How to easily remember Red-Black Tree insert and delete?

Question

It is quite easy to fully understand standard Binary Search Tree and its operations. Because of that understanding, I even don't need to remember the implementations of those insert, delete, search operations.

I am learning Red-Black Tree now and I understand its properties for keeping the tree balanced. However I feel very hard to understand its insert and delete procedures.

I understand when inserting a new node, we mark the node as red (because red is the best we can do to avoid breaking less Red-Black tree laws). The new red node may still break the "no continuous red nodes law". Then we fix it via:

1. check its uncle's colour, if red, then mark its parent and uncle as black, and go to grandparent.

2. if it is right child, left rotate its parent

3. mark its parent as black and its grandparent as red, then right rotate its grandparent.

done (basically like above).

Many places describes Red-Black tree's insert like above. They just tell you how to do it. But why those steps can fix the tree? Why first left rotate, and then right rotate?

Can anyone explains why to me more clearly, even more clear than CLRS? What's the magic of rotation?

I really wish to understand so after 1 year, I can implement Red-Black tree by myself without review a book.

Thanks

Answer 1

For the benefit of anybody else reading this thread who doesn't have access to the book mentioned in the accepted answer, here is what I hope will be an acceptable descriptive answer.

Rotating puts the tree in a state where it meets the criteria to recolor (the child node has a red uncle). There are two key differences:

• which node is the "child" and which node is the "uncle" has changed;
• instead of recoloring the parent and uncle to black and the grandparent to red, you recolor the parent to red, and the grandparent to black.

When the child node doesn't have a red uncle, you have to rotate because if the uncle node is already black, then making the parent black would increase the black height by 1 on only one side of the grandparent. This would violate the height invariant property of red-black trees and make the tree unbalanced.

Now let's look at how the rotation transforms the tree so that we have a child node with a red uncle and can use recoloring. I recommend drawing this out to fully understand it.

• Let x be the current red node with a red parent.
• Let p be the red parent of x before the rotation (if the parent was black, we'd be done already).
• Let y be the black uncle of x before the rotation (if the uncle was red, we wouldn't need a rotation. We'd simply recolor the parent and uncle to black and the grandparent to red).
• Let g be the black grandparent of x before the rotation (since the parent is red, the grandparent must be black; otherwise this was not a red-black tree to begin with.)
• When you have a left-left (LL) or right-right (RR) case (that is, x is the left child of p and p is the left child of g OR x is the right child of p and p is the right child of g), after a single rotation (right if LL, left if RR), y becomes the child and x its uncle. Since x is a red uncle, you now have a case where you can recolor. So, recolor the parent of the child (since the child is now y, its parent is g) to red, and the child's grandparent (which is now p) to black.
• When you have an LR (x is the left child or p and p is the right child of g) or RL case (x is the right child of p and p is the left child of g), after a double rotation (right then left if LR, left then right if RL), y becomes the child and p its uncle. Since p is a red uncle, you again have a case where you can recolor. So, recolor the parent (since the child is now y, its parent is g) to red, and the child's grandparent (which is now x) to black.

Before the rotation and recoloring, you had a black grandparent with 2 red nodes and 0 black nodes on side A (left or right) and 0 red nodes and 1 black node on side B (the opposite of side A). After the rotation and recoloring, you have a black grandparent with 1 red node and 0 black nodes on side A and 1 red node and 1 black node on side B. So you essentially moved one of the red nodes to the other sub-tree of the grandparent without increasing the black height of either sub-tree.

That's the magic of rotation. It allows you to move the extra red node to another branch without changing the black height, and still preserving the sorted traversal property of a binary search tree.

Answer 2

The logic is fairly simple. Suppose z is red and z's parent is red: If z's uncle is red, do step 1 to push the problematic node upwards until either (1) the parent becomes the root. Then simply mark the root black. Done or (2) z's uncle is black.

In case (2) either (a) z is the left child of its parent, then step 3 will be the last step as all properties of BST are fulfilled. Done. or (b) z is the right child of its parent. Step 2 will convert the problem to case (a). Then do step3. Done.

Thus the logic is to try to reach case (1) and (2a), whichever comes first. Those are the situations we know the solutions.