A Red-Black(RB) Tree is a self-balancing binary search tree. It maintains balance with the help of a few properties:
1. Every node is either red or black.
Every node is assigned a color.
2. The root and the leaves(nil’s) are all black.
Given a RB Tree, extend the existing leaves by adding two black children(which don’t have any value and hence called nil’s) for each of them. Root must always be black.
3. Every red node has a black parent.
Imposes a limit on the number of red nodes we can have in the tree. This is helpful because we will be working mostly with Red nodes.
4. All simple paths from a node x to some descendant leaf have the same number of black nodes = BlackHeight(x).
This and the previous property play a key role in the height balancing of the tree.
Example –
Height –
For n keys, the height h satisfies the relation:
h <= 2 * (log n + 1)
Proof –
I am trying to give an outline here. Merge all the red nodes back to their black parents. Now, we get what is called a 2,3,4 – tree where each node has 2,3 or 4 children. All leaves in this tree have uniform depth(remember BlackHeight? Property 4).
Let’s calculate the height h’ of this tree. We know that h’>= h/2 since at most half the nodes on any path are red. The number of leaves of a binary tree with n internal nodes = n + 1. This leads to:
2**h’ <= n + 1 -> h’ <= log(n + 1) [Taking log on both sides] -> h/2 <= log(n + 1) -> h <= 2*log(n+1) ~ O(log n)
Rotations
A picture is worth more than a thousand words :). The arrow from left-to-right shows the right rotation and the reverse denotes the left.
Left Rotation
void leftrotate(tree *t, node *x)
{
node *y;
node *nil = t->nil;
y = x->right;
x->right = y->left;
if(y->left != nil)
y->left->parent = x;
y->parent = x->parent;
if(x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
return ;
}
Right Rotation
void rightrotate(tree *t, node *x)
{
node *y;
node *nil = t->nil;
x = y->left;
y->left = x->right;
if(x->right != nil)
x->right->parent = y;
x->parent = y->parent;
if(y == y->parent->left)
y->parent->left = x;
else
y->parent->right = y;
x->right = y;
y->parent = x;
return ;
}
Insertion
Now that we learnt rotations, we will see how they are used in Insertion.
Given a node, it is colored red and inserted like it normally is inserted into a Binary Search Tree. Its easy to see that only property 3 will be violated. In order to balance this violation, we apply 3 cases and their reverse(interchanging left and right) as well.
color = 1 denotes red and color = 0 denotes black.
Code for insertion – http://pastebin.com/HQJn9QcB
Deletion
Deletion is similar to insertion but is slightly more complicated. CLRS is a good source for looking up the Delete and Delete Fix-up functions.
Applications
C++ STL containers map is implemented using Red-Black Trees.
Linux Kernel’s completely fair scheduler makes use of Red-Black Trees.
Problems
http://www.spoj.com/problems/ORDERSET/ – This problem can be solved by augmenting red black trees to store the information of how many times each value has occurred. Insertion and Deletion functions are the same. Kth smallest can be found by normal BST search with the count information.
Red-Black Trees can also solve many problems which can be solved using Heaps(the ones related to order statistics).
Inspiration
The inspiration for this post came after watching Erik Demaine’s lecture on Red-Black Trees – http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-10-red-black-trees-rotations-insertions-deletions/. What a lecture !
Code for Food 