今天把第五章的前半部分看完了， 感觉颇为失望。 侯捷想把RB-TREE的算法表达清楚， 虽然给出了很多好看的图示， 不过， 如果没有接触过RB-TREE， 看过后仍然会是一头雾水。
一个缺点就是把RB-TREE insertion搞复杂了。 在p211, 把一个case分成了两个来说， 而且没有必要的增加了rotation的操作。 一开始， 我很奇怪， STL是这样实现的吗？ 后来一看， 算法的实现跟CLRS上的一模一样。 有兴趣的朋友可以看看 CLRS （2nd english） p284 中的第一个case。
其次， 有意思的是， 侯捷并没有分析 RB-TREE delete的操作。 对于delete来说， 过程相对来说， 又要复杂一点。 这里记录一下：
当RB-TREE中的一个node被删除掉后， 有四中情况： （CLRS 2nd page 292）:
1. x's sibling w is red
2. x's sibling w is black, and both of w's children are black;
3. x's sibling w is black, w's left child is red, and w's right child is black;
4. x's sibling w is black, and w's right child is red.
7:59:16 PM Friday, May 15, 2009