algorithm - 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

question from:https://stackoverflow.com/questions/9469858/how-to-easily-remember-red-black-tree-insert-and-delete

Answer 1

ignore my (now deleted) comment - i think okasaki's code is going to help you. if you have the book ("purely functional data structures"), look at the text on page 26 and figure 3.5 (facing, p 27). it's hard to get clearer than that.

unfortunately the thesis available on-line doesn't have that part.

i'm not going to copy it out because the diagram is important, but it shows that all the different cases are basically the same thing, and it gives some very simple ML code that hammers that home.

[update] it looks like you may be able to see this on amazon. go to the book's page, mouse over the image and enter "red black" in the search box. that gives you results that include pages 25 and 26, but you need to be logged on to see them (apparently - i haven't tried logging in to check).