Our next self-balancing tree is the Red-Black Tree, which is another type of balanced binary search tree. Like AVL trees, Red-Black trees maintain balance through rotations during insertions and deletions, but they use a different set of rules based on coloring nodes red or black to ensure balance.
Below is a sample of a Red-Black tree. Note that the root node is black, red nodes have black children, and every path from the root to a null leaf has the same number of black nodes.
We often will not draw the null leaves in Red-Black trees, but it is important to remember that if we ever need to count black nodes along a path we must include those null leaves as black nodes.
Try using the Insert Random Values button a few times to build up a red-black tree. Click and drag to move the diagram around and examine the overall structure.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
The balancing process for Red-Black trees during insertions and deletions is more complex than for AVL trees, involving a series of color changes and rotations to restore the Red-Black properties. One way to understand the process is to think of each black node as representing a node in a B-tree of order 4. Red nodes are just part of the “group” that the black node represents.
When we insert in a red black tree, we start by inserting the new node as we would in a regular binary search tree, coloring the new node red. Then, we check for back up the tree to see if any of the Red-Black properties have been violated. If a violation is found, we perform a series of color changes and rotations to restore the properties.
If the parent of a red node is red, we have a violation. We then look at the uncle node (the sibling of the parent):
If the uncle is black (or null), that means we have a group of just three nodes. That can be fixed with rotations and recoloring:
Do a single or double rotation so that the median value of the three nodes becomes the new parent of the group.
If the uncle is red, that means we are in a logical group of 4 nodes (one black with two red children and a new red child for one of those). We fix this by recoloring the parent and uncle to black and the grandparent to red.
First try inserting 200 (type 200 into the Value text field and press Insert). Then use the > button to step through the insertion process. This new red node requires no adjustments as its parent is black.
Then reset and try adding 600. This adds a red node with a red parent, causing a violation that requires rotations and recoloring to fix. 600 requires a single rotation to fix. If you instead add 480, this will cause a zig-zag pattern requiring a double rotation.
Then add 950. This is a red child of a red parent (943) and a red uncle (800). Now the group rooted at 812 is overfull. So we “split” it by making the two red children (800 and 943) black and the grandparent (812) red. This logically adds the 812 node to the group centered at 726.
Finally, add 1. That should cause a similar group of 4 nodes that need to be split. 8 will become red, making it a part of the group that currently contains 50 and 134). Because that group now has a red child of a red node, but only has three total nodes, we can fix with a rotation.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
Similar rules govern removal of nodes from a Red-Black tree, however, the process is more complex. To see an example, reset the animation above and remove 134. This will end up removing a black node, which causes a violation of the property that every path to a null pointer must involve the same number of black nodes. The fix involves a series of color changes and rotations as we backtrack up the tree to restore balance.
Exhaustive treatment of the rules for a Red-Black tree are available in many online resources. Our key takeaway is that careful application of these rules can ensure that our tree follows the Red-Black properties as it is built and modified.
