红黑树–高效的二叉搜索树

2017-06-07 18:00 阅读 548 次 评论 0 条

红黑树与AVL树均属于高效的平衡二叉树,增删查改的时间复杂度都是0(logN),红黑树不追求完全平衡,保证了最长路径不超过最短路径的2倍,从而降低了旋转的要求。因此,在实际运用中,红黑树更胜一筹。

红黑树(RBTree)

概念:红黑树是一棵二叉搜索树,它在每个节点上增加了一个存储位来表示结点的颜色,红色和黑色,通过对任何一条从根节点到叶子结点上的简单路径来约束,且保证了最长路径不超过最多路径的两倍,因而近视平衡。

红黑树的5大性质(非常重要,理解透了再向下看):

1)每个节点不是红色就是黑色。

2)根节点一定是黑色的。

3)不存在两个连在一起的红色节点。

4)对于每个节点,从该节点到其所有后代叶子结点的简单路径上,均包含相同数目的黑色节点。

5)每个叶子结点都是黑色的(此处叶子结点指空节点)。

红黑树的插入

一般情况的插入:

1)如果插入的结点为根节点,直接插入,并将根节点的颜色赋为黑色。

2)如果插入的节点的父节点是黑色的,那么直接插入。

3)如果插入的结点的父节点是红色的,再次插入可能会造成两个红色节点相连的情况,下面我们就此类情况作以详细说明:

特殊情况的插入:此类插入动作存在6种情况,我们只针对前三种作以分析,后三种属于位置交换的场景。下列图示中,各节点的含义:

源代码及注释

红黑树的应用

红黑树作为一棵高效的二叉搜索树,用途非常广泛。比如C++STL库中的set、map、unorder_map、unorder_set;Java库、Linux内核 等都用到了红黑树。因此掌握红黑树是毋容置疑的,当然也不要忘记他的兄弟AVL树。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:红黑树–高效的二叉搜索树 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情