刚看完网易公开课上算法导论中的平衡搜索树,传送门,讲的真的炒鸡好,这里就稍微总结一下。
另一方面,视频是英文板书,在一些地方讲述有点慢,这时候就凸显了文章的优势了。

红黑树性质

红黑树的性质判定红黑树的充要条件,性质见下:

  1. 每个节点不是红色就是黑色。
  2. 根节点和叶子节点必须为黑色。
  3. 每个红色节点的父亲节点必须为黑色节点。
  4. 对于每个节点,在它到每一个子树的叶子节点的所有路径中,所经过的黑色节点数量相同。并定义这个数量为黑高(black height)。

补充一条推论,由性质3易得,一颗红黑树的红色节点不会超过总节点数的一半。
而对于第2条性质,我们一般会使最后指向的空节点染色成黑色即可。

红黑树的树高

先说结论,红黑树的树高 height 不会超过 $ 2log_2{(n+1)} $,即 $ height \leq 2 log_2{(n+1)} $。

证明如下:
将所有红色节点合并到其父亲节点,同时使该节点的孩子节点也合并成为其父亲节点的孩子节点。
这时候我们会得到一棵特别的树,它也是一棵平衡搜索树,称为2-3-4树。(建议在纸上画画)

2-3-4树有如下两条性质:

  1. 对于每个非叶子节点,它的孩子节点数量范围为[2,4]
  2. 对于每个叶子节点,它的深度都相同。

我们设由红黑树所得的2-3-4树的树高为 h',其叶子节点的数量为 leaf_num。可得不等式
$$ 2^{h’} \leq leaf_num \leq 4^{h’} $$
进而推导出 $ h’ \leq log_2{leaf_num} $

就剩下我们的leaf_num了,其实leaf_num和红黑树的叶子节点的数量是一样的,而一棵树的叶子节点的数量是这棵树的非叶子节点数量 + 1,这是显而易见的。而在我们的红黑树中,非叶子节点数量就是我们插入的元素数量 $ n $。
将其代入得$ h’ \leq log_2{(n+1)} $
最后再联系到我们最开始的目标,红黑树的树高height,因为我们只合并了红色节点,根据红黑树性质3的推论可得
$$ 2height \geq h’ $$
因此,$ height \leq 2log_2{(n+1)} $ 得证。

红黑树的查询

因为树高是在 log 级别,所以只要按照二叉搜索树的查找方法来即可。
复杂度上限为一个树高,即一个 log 。

红黑树的插入

省去引入与例子,直接讲解法。

首先插入时按照二叉搜索树的方法插入,将其染色为红色,这样不会影响树高,易修复,但可能会破坏性质3。

现在假设插入节点 x与其父亲节点p[x]都为红色,即破坏了性质3。

其修复步骤主要分2种情况,这里将之称为两个主要情况:

  1. 父亲节点是祖父节点的左孩子
  2. 父亲节点是祖父节点的右孩子

这两种主要情况下又分为三种次要情况,这里以上述主要情况1的条件下分类讨论:

  1. 祖父节点的右孩子p[p[x]].right,即叔叔(uncle)节点也为红色。此时让父亲节点和叔叔节点都染色成黑色,祖父节点染色成红色,将当前节点变更到祖父节点,进入下一个循环。
  2. 叔叔(uncle)节点为黑色,当前节点x为父亲节点p[x]的右孩子。此时将父亲节点左旋,使得进入情况3。
  3. 叔叔(uncle)节点为黑色,当前节点x为父亲节点p[x]的左孩子。可由情况2旋转得来。此时将祖父节点右旋并重新染色。染色方案为,新的祖父节点为黑色,新的父亲节点和新的叔叔节点为红色。退出循环。

而对于主要情况2,只要对主要情况1的3种次要情况做类似操作即可,唯一不同的就是方向反一下。
即 “左”–> “右”,“右”–> “左”。

红黑树的删除

视频没讲,有点晚了,明天看,并且补上C++代码实现。