Red-Black Trees
What are Red-Black Trees?
A Red-Black Tree is a variation of a Binary Search Tree that adds an extra attribute to each node - the node's color, which can be either RED or BLACK.
Why Do We Need Red-Black Trees?
The basic operations done on a Binary Search Tree (e.g. search, insert, etc.) are \(O(h)\) - they perform based on the height of the tree, so when the tree is balanced they perform optimally, but the height depends on the order that the nodes are inserted (and deleted) so the tree can end up being taller than we want it to be. Red-Black Trees use the colors and the Red-Black Properties to ensure that the tree is more balanced.
What are the Red-Black Properties?
These are the properties that need to be maintained for a Red-Black Tree to work correctly (from CLRS).
- Every Node is either Red or Black.
- The Root is Black.
- Every Leaf (Nil) is Black.
- If a Node is Red then both of its children are Black.
- For each Node, all simple paths from the node to descendant leaves contain the same number of Black Nodes.
When the properties are true the height of a tree with n nodes is \(O(\log(n))\).
What's the deal with the Nil Leaves?
CLRS define the leaves of a binary tree as Nil values (not the end nodes with keys like I tend to do) and for Red-Black Trees, unlike Binary Search Trees they use a special Node object that is colored Black and has arbitrary values for the other attributes. To save space the Nil Node is a singleton and besides being used as the leaves it also is the parent of the root.
Anything Else?
One last bit of terminology: the Black-Height of a node is the count of the Black Nodes on a simple path from the node to a leaf, not counting the node itself but counting the leaf. This is basically a name for property five of the Red-Black Properties.