DinS Written on 2017/5/21
This is the second part of RedBlack Tree. See first part here.
5. Insert
Insertion in red-black tree is hard. Not only do we need to consider Search Tree Property, but we also need to think about red-black property now. The idea is to proceed as in a normal binary search tree, and then do some recolor and rotations until the rules are restored. The steps are as follows:
(1) Apply the same insertion method in B.S.T. Now we face a dilemma: if the node is red, rule #3 may be broken; if the node is black, rule #4 may be broken.
(2) Paint node x red. This is to choose the less of two evils, because compared with black node, red node can only have local consequences.
(3) if x’s parent node p is black, the done. Rule #3 maintained.
(4) else x’s parent is red, which means p has a black parent g. Here we encounter the double red problem. Now depending on the color of the other child of g, which I’ll call u, as uncle to x, there’re two cases.
Case I: u is black or null. In this case we do some rotations and recoloring to fix the problem. If x, p, g are in a straight line, we left/right rotate g and paint p as black and g as red. If x, p, g are in a zigzag position, we left/right rotate p and then right/left rotate g, and paint x as black and g as red.
Here is a demonstration of the straight-line adjustment. (Notice that u may be null)
We should notice that before the adjustment:
i. the path from subtree A to upper tree passes p -> g with one black node g;
ii. the path from null(p) to upper tree passes p -> g with one black node g;
iii. the path from subtree B to upper tree passes u -> g with two black nodes u, g;
iv. the path from subtree C to upper tree passes u -> g with two black nodes u, g.
After the adjustment:
i. the path from subtree A to upper tree passes g -> p with one black node p;
ii. the path from null(x) to upper tree passes x -> p with one black nodes p;
iii. the path from subtree B to upper tree passes u -> g -> p with two black nodes u, p;
iv. the path from subtree C to upper tree passes u -> g -> p with two black nodes u, p.
All paths pass the same number of black nodes as before. Since before the adjustment the tree is a red-black tree and rule #4 is valid, as a result after the adjustment rule #4 is maintained. Besides we have solved the double red problem.
Here is a demonstration of the zigzag-position adjustment. (Notice that u may be null)
We should notice that before the adjustment:
i. the path from subtree A to upper tree passes p -> g with one black node g;
ii. the path from null(p) to upper tree passes p -> g with one black nodes g;
iii. the path from subtree B to upper tree passes u -> g with two black nodes u, g;
iv. the path from subtree C to upper tree passes u -> g with two black nodes u, g.
After the adjustment:
i. the path from subtree A to upper tree passes p -> x with one black node x;
ii. the path from null(p) to upper tree passes p -> x with one black node x;
iii. the path from subtree B to upper tree passes u -> g -> x with two black nodes u, x;
iv. the path from subtree C to upper tree passes u -> g -> x with two black nodes u, x.
But the tricky part is this: we have an extra path from null(g) to upper tree. Does this new path spoil the whole tree? To answer this question, let’s go back to pre-insertion stage. Node x didn’t exist. This means from null(p) to upper tree passes one black node. I’ll mark it as “upper + 1”. Besides, the tree is a red-black tree, which means all paths have “upper + 1”. Now after the adjustment the path from null(g) to upper tree also has “upper + 1”, the same as null(p) to upper trees. In conclusion this doesn’t break rule #4.
Case II: u is red. In this case we do some (and maybe more) recoloring to fix the problem. Concretely we paint p and u black, and paint g red, regardless of their positions. Now we either restore Rule #3, which means that g’s parent is black, or propagate the double red problem upward. During propagation we may encounter case I or case II, but now we have the method to solve these. Propagation may happen O(logn) times. If we reach the root, we recolor it black. Done.
Here is a demonstration of case II.
To see the correctness of the recoloring method, note that before recoloring all paths pass one black node g. After recoloring all paths also pass one black node, either p or u. This means Rule #4 is maintained.
Abstract enough, right? Now let’s look at a concrete example of insertion in red-black tree. As usual, let’s summon this big tree from the beginning of this article, with a little change in the value of one node. Don’t worry; the change is only to help us bring out more variations in the process of insertion.
Now I want to insert node 44 in this tree. According to the rule we insert it in the right position and paint it red. Here is what it looks like.
The new node’s parent is black. No rule is broken, done!
But I know you are not satisfied. This is just too plain! Now let’s continue to insert node 45 and see what will happen.
We encountered double red problem. Upon closer inspection, this belongs to case II. To solve it we need to recolor node 42 and 44 black, and node 43 red.
But the problem continues to exist. We only propagated it upward. The current problem is node 43. Upon closer inspection we know that this belongs to case I, zigzag position. To solve it we need to do some rotations and recoloring.
Concretely we first left rotate node 39 and then right rotate node 47. Now we get this tree.
Then we recolor node 43 black and node 47 red. Finally we get this tree.
Let’s do some examination. After insertion the root-null paths should all pass 3 black nodes like before. Since the insertion only affects the subtree of node 43, let’s check it out.
Rule #4 is maintained. We did it!
Finally, efficiency. Whether it is case I or case II, combined together we have to do at most O(logn) recoloring and O(1) rotations. This means O(logn) for insertion and constant times in topological structure change, as promised.
This article continues at RedBlack Tree – Part C.