Walkthrough of red-black trees with example

First of all, red-black trees are only a representation of 2-4 trees. The reason for this is because the red-black trees are easier to implement into code. We're not going to look at implementing red-black trees into code in this post, but rather some of the theory behind red-black trees.

For red-black trees there's some rules.

• A node is either red or black
• A new node is always red
• Root node or leaves are always black
• A red node can not have a red parent or a red child
• Every path from the root to a nullptr node will have the same number of black nodes
• If the aunt is red, the father is red, and the daughter is red. Then what we must do is a color change. Where the aunt and father shall be black and the grandparent shall be red

As an example, we can look at how we will build a red-black tree for the list 1, 2, 3, 4, 5, 6.

We will start with the root node that has to always be black. From there on we will add 2 which will become a red node, because each new node has to be red. If a new node (A red one) breaks the rules for red-black tree, we will have to do a rotation or recolor the node. As of currently, we haven't made a breach to our red-black tree, so we will add a new node.

We can now see that we've breached the rules by adding the new node. In this case, we can't just recolor the newest node, because that will again result in us breaking the rules. So we must do a rotation in order to get a valid red-black tree. After the rotation, we will also need to recolor the root node black in order to stay true to the rules.

Now if we are to set in the next node we will again get an error. But in this case we will have to recolor the nodes properly. Which we will use a rule for.

If the aunt is red, the father is red, and the daughter is red. Then what we must do is a color change. Where the aunt and father shall be black and the grandparent shall be red. We will then up with a tree that looks like this.

But there's an error here! The root node is now red, and we are not allowed to have our root node red. It must be black. So we must recolor it black. Let's also add the next node while doing that.

We will now also have another error. The node 4 has a red child, which is not permitted. That means that we have to left rotate.

Now that we have successfully done our rotation and color change. We can add the last element to our red-black tree, namely the 6.

We got another error! The problem is that node 5 has a red child, namely 6. We must recolor with the rule we used above.

We have now successfully completed our red-black tree for our list 1, 2, 3, 4, 5, 6.

A little sidenote is that the University of San Fransisco has a great interactive web application for solving red-black trees, found under https://www.cs.usfca.edu/~galles/visualization/RedBlack.html.