一、红黑树介绍

红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和 Robert Sedgewick改成一个比较摩登的名字:红黑树。

 

二、红黑树与AVL树比较

红黑树AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。
红黑树和AVL树的区别:红黑树使用颜色来标识结点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。

 

三、红黑树的工作原理

使用红黑树的主要目的是在一定的控制范围内保持二叉树的平衡,保持了二叉树的平衡便能达到更好的查找效率。
那么红黑树是如何使二叉树达到平衡的呢? 红黑树没有使用二叉平衡树那种严格的平衡准则,红黑树使二叉树平衡是靠自身的红黑树规则来实现的,下面是红黑树的规则(共四条):

(1) 每个结点的颜色只能是红色或黑色,且根结点一定是黑色的。
(2) 如果一个结点是红的,则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点,只要有一个红节点,它的父节点和子节点必然都是黑色的。
(3 )对于每个结点来说,从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。
(4 )每个叶子结点都带有两个空的黑色结点(被称为黑哨兵),如果一个结点的只有一个左孩子,那么这个节点右孩子是一个黑哨兵;如果这个节点只有一个右孩子,那么这个节点的左孩子是一个黑哨兵。没有孩子节点的地方,都被黑哨兵填充,目的是为了是红黑树为满足第3条规则进行限制。

红黑树的这4个性质中,第4点是比较难理解的,但它却非常有必要。我们看下面左边这张图,如果不使用黑哨兵,它完全满足红黑树性质,结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但如果加入黑哨兵后(如右图中的小黑圆点),叶结点的个数变为8个黑哨兵,根结点50到这8个叶结点路径上的黑高度就不一样了,所以它并不是一棵红黑树。

图 红黑树示例

思考这样一个问题: 通过上面的性质为什么能使二叉树保持一定的平衡呢?
通过性质3可以知道:从根节点到叶节点路径上的黑色节点的数目均为n,于是,红黑树的最短路径为全黑,即“黑 –> 黑 –>......... 黑 –> 黑”,即最短路径长度为n-1(相邻节点间的距离为1),而最长路径只能取为红黑交替“黑 –> 红 –>......... 红 –> 黑”,这样可使黑色节点数量最多,即最长路径为2(n-1)。通过上面的分析可以得出:在红黑树的所有从根节点到叶节点的路径中,最长路径不会超过最短路径的2倍。
可见,红黑树使用红黑二色进行“着色”,目的是利用颜色值做二叉树的平衡对称性的检查,只要插入的节点“着色”满足红黑二色的规定,最短路径与最长路径不会相差太远,红色树的节点分布就能大体上达到平衡。当然这种平衡时一种有所放宽的平衡。

 

四、红黑树插入删除简介
    红黑树的插入和删除过程比较复杂,具体过程留在后面进行总结。总体上来说,红黑树在插入一个节点的时候,会将插入的节点着色为红色,然后再检查红黑树定义的规则是否被破坏,如果破坏需要对子树进行左右旋转,这里的旋转也涉及到LL、LR、RR、RL四种旋转方式。
红黑树的删除比插入更为复杂,这里不进行介绍。

 

五、红黑树的性能

一个有n个节点的红黑树的高度最大为2log(n + 1)  (算法导论上证明)。在红黑树中查找、插入、删除的时间为O(log n),其中n是树种元素的数目.