After rereading the chapter on binary search tree (Chapter 12), I think I finally grok deletion. In fact there are two non-trivial issues of binary search tree, one is to find a successor node when the right node is empty. (In that case, you are always look for an ancestor whose left child is also an ancestor of the node.
The other is in deletion of a node with two child nodes, you always want to delete the tree-minimum of the right sub tree. Once these two issues are thought through, you understand all operations of binary trees. (The others are more like simple recursive thinking).
Another good news is that I also reread red-black tree, this time, it starts to make sense on why we have this funny color fix-up algorithm. The most important is to visualize the two different cases where the red-black properties should be handled. I don't really grok at this point but I think I understand way more. It is super-complicated but it's also how the thing should work. I stopped at deletion because it is even more complicated.
It's funny to see the whole business of building a balanced tree is so difficult. This read is good. I also finished in my head some exercises.
No comments:
Post a Comment