本文转载自:http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html 前面一篇文章介绍了2-3查找树,可以看到,2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgN,从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂,本文介绍一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree) 定义 红黑树的主要是想对2-3查找树进行编码,尤其是对2-3查找树中的3-nod…

2021年3月7日 0条评论 35点热度 阅读全文

红黑树 1.概述 定义 由红、黑两色节点组成的二叉搜索树若满足以下条件,即为红黑树 (red-black tree):    (1) 树根始终为黑色    (2) 外部节点均为黑色    (3) 其余节点若为红色,则其孩子节点必为黑色    (4) 从任一外部节点到根节点的沿途,黑节点的数目相等   从以上条件可得:红节点均为内部节点,且其父节点及左、右孩子必然存在。红节点之父必为黑色,因此树中任一通路都不含相邻的红节点。 &…

2021年3月7日 0条评论 20点热度 阅读全文

红黑树属于平衡二叉树,所以很多操作根二叉树是一样的。学习红黑树,首先要把二叉树理解,并能用代码实现。   我主要讲述我是怎么写一棵红黑树的,并不做过细的解释。我们主要学习旋转,插入,删除。其他操作根二叉树是一样的。   旋转跟插入操作,我是跟STL源码剖析学的,书上讲的很清楚,一个上午就可以理解+实现,然后下午学习删除操作,呵呵。。。删除操作书中没有介绍,我是对照算法导论里的伪代码跟在网上找的代码学的。不过有的博客里的源码有错误,建议大家先把他的代码粘下来,然后多运行两便,确定没问题后再跟他的代码学习。   接下来…

2021年3月7日 0条评论 33点热度 阅读全文

红黑树和B树应用场景有何不同? 2者都是有序数据结构,可用作数据容器。 红黑树多用在内部排序,即全放在内存中的,微软STL的map和set的内部实现就是红黑树。 B树多用在内存里放不下,大部分数据存储在外存上时。因为B树层数少,因此可以确保每次操作,读取磁盘的次数尽可能的少。 在数据较小,可以完全放到内存中时,红黑树的时间复杂度比B树低。 反之,数据量较大,外存中占主要部分时,B树因其读磁盘次数少,而具有更快的速度。 红黑树,B树,B+树,B-树 理解 红黑树rbtree 二叉排序树 map 就是采用红黑树存储的,…

2021年3月7日 0条评论 37点热度 阅读全文

今天看了STL源码剖析中关于红黑树的原理和实现,看完复杂的节点插入、节点颜色变换后不禁想:这些功能经典的AVL树也能实现,为什么要提出红黑树?查了些资料,并且加上自己理解,感叹红黑树的巧妙。 首先红黑树是不符合AVL树的平衡条件的,即每个节点的左子树和右子树的高度最多差1的二叉查找树。但是提出了为节点增加颜色,红黑是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。所以红黑树的插入效率更高!!!…

2021年3月7日 0条评论 51点热度 阅读全文

平衡二叉搜索树的形式多样,且各具特色。比如,伸展树实现简便、无需修改节点 结构、分摊复杂度低,但可惜最坏情况下的单次操作需要n时间,故难以适用于对可靠性和稳定性要求极高的场合。 反之,AVL树尽管可以保证最坏情况下的单次操作速度,但需在节点中嵌入平衡因子等标识;更重要的是,删除操作之后的重平衡可能需做多达logn次旋转,从而频繁地导致全树整体拓扑结构的大幅度变化。 红黑树即是针对后一不足的改进。通过为节点指定颜色,并巧妙地动态调整,红黑树可保证: 在每次插入或删除操作之后的重平衡过程中,全树拓扑结构的更新仅涉及常数…

2021年3月7日 0条评论 33点热度 阅读全文

红黑树学习笔记 红黑树的5个性质 红黑树的插入 红黑树的删除 红黑树学习笔记 红黑树的5个性质 每个结点要么是红的,要么是黑的。 根结点是黑的。 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。 如果一个结点是红的,那么它的俩个儿子都是黑的。 对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。 注意黑色的nil结点,对于红黑树的删除的理解很重要。 红黑树的插入 插入一个初始为红色的节点,有以下3种情况。 1.空树,使其颜色转为黑,成为根。 2.父为黑,无须调整。 3.父为…

2021年3月7日 0条评论 20点热度 阅读全文

关于红黑树和AVL树,以下哪种说法不正确? 正确答案: D   你的答案: 空 (错误) 两者都属于自平衡二叉树 两者查找,插入,删除的时间复杂度相同 包含n个内部节点的红黑树的高度是O(log(n)) JDK的TreeMap是一个AVL的实现 添加笔记 求解答(14) 收藏 纠错 关于红黑树和AVL树,来自网络: 1 好处 及 用途         红黑树 并不追求“完全平衡 ”——它…

2021年3月7日 0条评论 69点热度 阅读全文

原文出处http://cmsblogs.com/ 『chenssy』 在【死磕Java并发】—–J.U.C之Java并发容器:ConcurrentHashMap一文中详细阐述了ConcurrentHashMap的实现过程,其中有提到在put操作时,如果发现链表结构中的元素超过了TREEIFY_THRESHOLD(默认为8),则会把链表转换为红黑树,已便于提高查询效率。代码如下: if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); 下面博主将详细分析整个…

2021年3月7日 0条评论 25点热度 阅读全文

1、红黑树的性质(参考《算法导论》): 每个节点均有颜色属性,且要么为红色,要么为黑色; 根节点为黑色; 红色节点的子节点不可以为红色 对每个节点,从该节点到期子孙节点的所有路径上包含相同数目的黑节点 2、红黑树节点的定义: <span style="font-family:Courier New;">template <typename T> class RBTNode { private: T data; char color; RBTNode<T> *lchild; RBT…

2021年3月7日 0条评论 17点热度 阅读全文