Upgrading, In Color
How It Works
The Red-Black tree adds an extra data item to each node that is the color for that node, and it adds a third reference to the parent of each node. As you might imagine, the colors are red and black. With this small addition, there are four rules that are followed to create a self-balancing tree. The data is added to the tree as a red node in the normal way for BST trees and, after the insertion, the tree is readjusted according to the four rules.
The rules are:
- Every node will have a color, red or black (we knew that)
- The root node must be black
- Red nodes may not be vertically adjacent anywhere in the tree. This means that a parent and its child node may never be red.
- The number of black nodes must always be the same when counting from any given node to the bottom of the tree following any branching path
There are a series of operations that support compliance with these four rules but they are pretty simple to follow in a recipe- or algorithm- like operation. Since the resolution process is called after the insertion process, it does require climbing the tree from where the new node was added so this is why a parent reference is required. A Red Black tree will allow a maximum difference in tree height of two, meaning none of the lowest leaves will have a height difference greater than two.
Before moving on, there is a web page you should be familiar with that handles all kinds of data structures in a graphical way. The web site can be found here. It is very worth your while to look at, and play with, this reference to learn more about most data structures, including this Red-Black tree.
Future
This topic will be completed at a future point.