红黑树<一>

[ccb1900]

来自算法导论

来自维基百科

常见的树操作有插入，查找，删除，求最大值，最小值等，时间复杂度都是O(h)，其中h是树的高度。所以h的值越小，完成这些操作需要的时间也就越少。如果h的值较大，那么这些操作的速度可能还不如链表。红黑树是许多平衡树的一种，在最坏的情况下，这些操作完成的时间复杂度为O(lgn)。

什么是红黑树

红黑树是二叉搜索树。因此具有二叉树的所有性质。它在每个节点上增加了一个存储位，用来表示颜色，这个颜色可能是红色或者黑色。通过对任何一条从根到叶子节点的简单路径上各个节点颜色进行约束，红黑树确保没有一条路径比其他路径长两倍，因此是近似平衡的。

红黑树中每个节点包含五个属性，颜色，关键字，左指针，右指针，p。如果一个节点没有子节点或者父节点，则该节点相应指针属性为nil。我们可以把这些nil视为指向二叉搜索树的叶子节点(外部节点)的指针，而把带关键字的节点视为树的内部节点。

假设指向叶子节点的指针nil是不同的，如下图。

红黑树的性质

1. 每个节点都有颜色，红色或者黑色。
2. 根节点是黑色的。
3. 每个叶子节点是黑色的（nil节点）
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 对每一个节点，从该节点到其所有后台叶节点的简单路径上，均包含相同数目的黑色节点。

为了便于处理红黑树代码中的边界调价，使用一个哨兵来代表 nil 。对于一课红黑树T，哨兵T.nil是一个与树中普通节点有相同属性的对象。它的颜色是黑色的，而其他属性可以设置为任意值。所有指向nil的指针都用指向哨兵的T.nil替换。

因此我们得到了下图。

黑高

简单路径上黑色节点的个数就是黑高。红黑树的黑高就是根节点的黑高。 一棵有n个内部节点的红黑树的高度最多为2lg(n+1)。

应用场景

• 关联数组实现
• 集合实现
• 与阶为4的B树-2-3-4树等同

参考

维基百科 算法导论