红黑树

一棵高度为h的二叉搜索树，可以支持任何一种动态集合操作，如SEARCH、PREDECESSOR、SUCCESSOR、MINIMUM、MAXIMUM、INSERT和DELETE，其平均时间为$O(h)$。如果搜索树的高度较低时，这些集合操作会执行地很快。然而如果树的高度比较高时，这些集合操作可能并不比在链表上执行地更快。红黑树可以保证在最坏情况下基本动态集合操作的时间复杂度$O(lgn)$。

平衡二叉树（AVL树）的追求的是全局均衡，如在做插入，删除操作时，需要调整整棵树，显然这是费时的，因此希望在做调整时，是局部调整，因此提出了红黑树，这样一种高效的数据结构。

红黑树属于非严格意义上的平衡二叉树，说它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1。但红黑树高度依然是平均log(n)，且最坏情况高度不会超过2log(N+1)，这有数学证明。所以它算平衡树，只是不严格。不过严格与否并不影响数据结构的复杂度。

红黑树是一棵二叉搜索树，树中每个结点包含5个属性：color、key、left、right和parent。结点的颜色可以是黑色，也可以是红色。通过对任何一条从根到叶子的简单路径上每个结点的颜色进行约束，红黑树能够确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。

 

如果一个结点没有子结点或父结点，则该结点相应指针属相的值为NIL。可以将这些NIL视为指向二叉搜索树中的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。

红黑树性质：

• 根节点是黑色的。
• 每个叶结点(NIL)是黑色的。
• 如果一个结点是红色的，则它的两个子结点是黑色的。
• 任一结点到其所有后代叶结点(NIL)的简单路径上，所含之黑色结点数相同。

使用一个哨兵来代表NIL。T.nil是一个与树中普通结点有相同属性的对象。它的color属性为BLACK，而其他属性parent、left、right和key可以设置任意值。所有指向NIL的指针可以用指向哨兵T.nil的指针替换。如图(b)所示。

使用一个哨兵T.nil来代表所有的NIL：所有的叶结点和根节点的父结点。哨兵的属性parent、left、right和key的取值并不重要。通常我们将注意力只放在红黑树的内部结点上。

从某个结点$x$出发（不包含该结点）的任意一条简单路径上的黑色结点个数（包含叶结点T.nil的个数，在图(c)中没有画出来） 称为该结点的黑高(black-height)，记为$bh(x)$。

引理1、一棵有n个内部结点的红黑树的高度至多为$2log(n+1)$

证明：以任一结点x为根的子树中至少包含$2^{bh(x)}-1$个内部结点。（可用数学归纳法证明）

同时，设$h$为树的高度，根据性质3，从根到叶结点（不包含叶结点）的任何一条简单路径上都至少有一半的结点为黑色。因此，根的黑高至少为$h/2$。

所以$n\ge 2^{h/2}-1$，从而$h\leq 2lg(n+1)$。

由该引理可知，SEARCH、PREDECESSOR、SUCCESSOR、MINIMUM、MAXIMUM在红黑树上在$O(lgn)$时间内执行。

 

其中，红色节点用双圈表示。

虽然当给定一棵红黑树作为输入时，二叉搜索树的TREE-INSERT和TREE-DELETE的运行时间为$O(lgn)$，但是这两个算法并不直接支持动态集合操作INSERT和DELETE。因为它们并不能保证被这些操作修改过的二叉搜索树仍是红黑树。这个时候就需要旋转。

根据二叉搜索树的规则，新结点$X$必须为叶结点，根据红黑树规则4，X必为红（任一结点到叶结点的黑高相同）。若Parent亦为红，则违反了规则3（如果一个结点是红色的，则它的两个子结点是黑色的），则Grandfather必为黑（因为原为RB-TREE，必须遵守规则3）。

 

如果新插入的项的父节点是黑色的，那么插入完成。

如果父节点是红色的，那么需要考虑以下几种情况。

状况1、2：伯父节点S为黑色（规定NIL节点为黑色）且X为外侧插入（伯父节点S为黑色（规定NIL节点为黑色）且X为内侧插入）。对P，G做一次单旋转，X为新加的叶结点，这种情况下X和P为红色，G为黑色，否则会在插入前有两个相连的红色结点。X、P和G构成一字型或之字型。第一种情形对应P和G之间的单旋转，而第二种情况对应双旋转（LR型）：两次单旋转，先对G的左孩子(P)做逆时针(RightChildSingleRotation)，后顺(LeftChildSingleRotation)。

注意：必须记录父节点（P）、祖父节点（G），以及为了重新连接还要记录曾祖父节点（GG）。交换P、G颜色。也就是子树的新根均被涂为黑色。因此，即使原来的曾祖父是红色的，也不可能会有两个相邻红色节点。同时，通向A、B、C诸路径上的黑色节点个数保持不变。

状况3、4：伯父节点S为红色（规定NIL节点为黑色）且X为外侧插入。对P，G做一次单旋转，并改变X的颜色（黑色），P为红色。如果GG为黑色，则插入完成。但如果GG为红色，则需要持续往上做旋转，直到不再有两个相连的红色结点或者到达根节点（它将被重新涂成黑色）。

 自顶向下红黑树

上滤的实现需要用一个栈或用一些父链保存路径。为了避免状况4“父子节点皆为红色”的情况持续向RB-TREE的上层结构发展，可以施行一个自顶向下的春程序：在向下的过程中看到节点X有两个红色儿子节点的时候，让X变为红色的，而让它的儿子节点是黑色的。