在之前一篇文章里，我提到学会 AVL tree 或者 b tree 的重要性。后来在基础班的讨论会，有同学说他还听说过「红黑树」（red-black tree），问我红黑树和 AVL tree 有什么差别。我只告诉他红黑树是“随机的”，并不是精确地平衡的，所以查找效率没有 AVL tree 那么有保证。
为什么人们怕写 AVL tree
其实我没写过红黑树。最早的时候我学的是 AVL tree，并实现过它。虽然我实现过 AVL tree，但当时觉得很麻烦，容易弄错，所以我之前害怕写它。因为对 AVL tree 的恐惧，又听说红黑树更简单，而且好像效率差不多，就以为红黑树是好东西。后来每次看书上讲的红黑树，都没看明白它是怎么回事，也没动手实现过红黑树。然而我仍然觉得红黑树比 AVL tree 好，因为人们都…