追来者之人

红黑树

一、什么是红黑树？

红黑树是一棵只有红色节点和黑色节点的平衡二叉搜索树。

其结构类似这样：

      b4
   /      \  
  r2      r6
 /  \    /  \
b1  b3  b5  b7
              \
              r9

其中，b 表示黑色，r 表示红色。

1.1 红黑树的特性

在《算法导论》里，红黑树是这样定义的：