- 综合排序
- 最热优先
- 最新优先
- 来自专栏每天学Java
红黑树(一):构建红黑树
平衡二叉树 红黑树 红黑树属于平衡二叉树，但是并非严格意义上的平衡二叉树，因为平衡二叉树要求节点的左右子树高度差不超过1， 而红黑树放弃了这种高度平衡，利用对结点上色的操作来保证树相对平衡，这其中原因大概是维护一个绝对平衡的二叉树代价太大 但如果插入频率小或者只有一次构建，那么平衡二叉树的查询性能还是比红黑树高。 此时红黑树构建平衡分为4种情况: 情况一:红黑树为空树，此时插入结点充当根结点，上色为黑 情况二:插入结点已经存在，此时替换插入结点值即可 情况三:插入结点的位置，其父结点是黑色，此时平衡未打破，插入完成 构建过程 我们依次插入1，-1，-2，-3，2，5，4，3来看一下红黑树的构建的过程 插入1，构建根结点:情况一 ? 插入-1，构建孩子结点:情况三 ? 插入-2，失衡，情况4.1 ? 到这里就构建完成了 相对于构建新增，红黑树的删除情况更为复杂，由于时间关系(这周只有一天休息加上绘图太费劲)，留到下一次分享。 构建代码 红黑树构建源码
2.1K42发布于 2020-06-01 - 来自专栏Android知识点总结
2-3树与红黑树
第一次接触红黑树是在关于hashMap，上来就扔五个特性，说满足这五个特点的二分搜索树就是红黑树。 （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 瞬时懵逼……我扔十个特性，是不是能定义一个红绿灯树呢。所以一直不明白红黑树为什么要这么定义。 直到今天了解了2-3树，才豁然开朗。2-3树是一种神奇的树，它能够保证该树是一个完美树。2-3树可以演化成红黑树，这便是保证红黑树效率的根本。 先说奇葩的2-3树，首先2-3树满足二分搜索树，但每个节点可能存在1或2个数据，对应的该节点就可能存在2或3个子节点 2-3树 ? 2-3树引入.png 2-3树插入操作： ? 2-3树.png 2-3树演化为红黑树 将三节点拆为两个节点，并将左数据节点设为红色来实现2-3树同等功能 ? 红黑树.png
59330发布于 2018-09-29 - 来自专栏机械之心
红黑树
这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。 # 什么是红黑树 红黑树的英文是 “Red-Black Tree”，简称 R-B Tree。 红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。 所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。 # 红黑树平衡调整 # 插入操作的平衡调整 红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。 # 参考资料 数据结构与算法之美 数据结构 树 二叉树 红黑树
74210编辑于 2023-04-07 - 来自专栏LeetCode
红黑树
红黑树的介绍 红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。 红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。 除了具备该特性之外，红黑树还包括许多额外的信息。 红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。 红黑树的特性: (1) 每个节点或者是黑色，或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。 (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 关于它的特性，需要注意的是： 第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。 因而，红黑树是相对是接近平衡的二叉树。
1K00发布于 2019-03-03 - 来自专栏魔法书
红黑树
什么是红黑树 红黑树依然是一棵二分搜索树，《算法导论》中的红黑树定义如下： 每个节点或者是红色的，或者是黑色的 根节点是黑色的 每一个叶子节点（最后的空节点）是黑色的 如果一个节点是红色的，那么他的孩子节点都是黑色的 从任意一个节点到叶子节点，经过的黑色节点是一样的 在学习红黑树之前，我们有必要先学习一下什么是2-3树，学习2-3树不仅对于理解红黑树有帮助，对于理解B类树，也是有巨大帮助的。 如下图所示： 红黑树与2-3树的等价性 我们在这里定义所有的红色节点都是向左倾斜的，红色节点代表与父亲节点相融合，由于我们可以通过2-3树画出一个棵红黑树： 由此可知，红黑树是保持“ 红黑树和AVL树：由于红黑树的最大高度是2logn,所以在查找时，相比于AVL树会慢一些，而红黑树的添加和删除元素比AVL树更快一些，如果只是用于查询，AVL树的性能要更高一些。 向红黑树中添加一个新元素，类比于2-3树中添加一个新元素，就是或者添加进2-节点，形成3-节点；或者添加进3-节点，暂时形成一个4-节点，这样我们可以让我们的红黑树，永远添加红节点。
54210编辑于 2024-01-19 - 来自专栏码云大作战
红黑树
在JDK8之前其实就已经有红黑树的应用，比如TreeMap的底层就是用了红黑树的数据结构。本文主要是为了讲解JDK8中HashMap底层数据结构的铺垫。 （3）左右子树也是一个二叉查找树。 · 示例 根据BST的特点，来生成一个二叉查找树。 给一组随机数，[5、9、10、8、3、4、1]，观察生成二叉查找树的过程。 （3）8>5，8<9，根据BST特点一，因此8为9的左孩子。 ? （4）3<5，根据BST特点一，因此3为5的左孩子。 ? （5）依次类推，形成最后的二叉查找树。 ? 再经过变色后，形成最终的红黑树： ? 三、总结 个人觉得红黑树是一个挺不错的思想，红黑树在BST的基础上还引入了颜色的特点，通过变色和旋转来保持红黑树的特点，保证树的平衡。 红黑树的前身其实是234树，有兴趣的小伙伴可以了解下234树，234树和红黑树的操作完全是等价的。之所以在java中使用红黑树的数据结构是因为如果直接使用234树实现会非常繁琐。
98020发布于 2020-08-26 - 来自专栏芝士就是菜
红黑树
红黑树概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。 红黑树的性质 每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的，则它的两个孩子结点是黑色的，树中没有连续的红节点 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径中节点个数的两倍？ 插入 红黑树的叔叔是关键 u存在且为红，变色继续向上处理 u不存在或存在且为黑，旋转（单旋+双旋）+变色 情况一：cur为红，parent为红，grandfather为黑（固定），uncle存在且为红
89420编辑于 2023-04-20 - 来自专栏shysh95
红黑树
下面我们会红黑树的特征、插入以及删除来分析红黑树是如何进行自平衡的。 特征 想要了解红黑树如何自平衡，就必须了解红黑树的特征，因为自平衡操作都是围绕这些特征来的，一旦一个红黑树因为插入和删除节点打破了自身的特征，那么他就需要进行自平衡(变色、旋转)来使得二叉树重新满足红黑树的特征 通过上述特征，决定了红黑树的一个重要特性：从根到叶子的最长的可能路径不多于最短路径的两倍长。 下图是一张红黑树示意图： ? 当我们插入节点时需要，红黑树的特征可能会遇到以下情况： 性质1和性质3总是保持着。 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。 ，需要我们细细揣摩，并且反复的研究，在了解红黑树的基本概念以后，我们后续会分析一下HashMap中红黑树的实现以及着手自己实现一个红黑树。
1.3K20发布于 2020-05-26 - 来自专栏爱编码
红黑树
前言 红黑树的应用还是比较广泛的。比如Java8的HashMap的底层就用到了红黑树，还有TreeMap和TreeSet也用到了。 下面主要以下几个方面学习一下红黑树。 1）二叉查找树BST 2）红黑树RBTree的规则、增删查 3）红黑树的Java实现。 其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。 特征 除了符合二叉查找树的特征以外，红黑树还有以下特征： 1、节点是红色或黑色。 2、根节点是黑色。 3、每个叶子节点都是黑色的空节点（NIL节点）。 4、每个红色节点的两个子节点都是黑色。 下图中这棵树，就是一颗典型的红黑树： ? 什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子： 添加节点 1.向原红黑树插入值为14的新节点： ?
1.1K31发布于 2019-08-06 - 来自专栏编程从踩坑到跳坑
红黑树
在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。 对于"特性(3)"，显然不会违背了。 case2很简单，通过旋转生成右边的图，而右边的情况就是case3。 总之case2就是通过一次旋转，然后进行case3的判断 3. (Case 3)叔叔是黑色，且当前节点是左孩子 ? 总结： 红黑树的插入操作，当父节点为黑时，很好理解。主要是当父节点是红色时，需要区分成3种case。 case2时，发生一次旋转操作，跳到case3情形。 case3时，发生一次旋转操作，再一次着色操作。完成操作。 所以红黑树的选择操作很少。局部至多2次（插入最多两次旋转，删除最多三次旋转）。 -3树,2-4树都可以转化成红黑树，红黑树能达到O(logn)高度，但是不像AVL树那样严格要求左右子树高度差必需相差不超过1。
1K40发布于 2019-12-20 - 来自专栏计算机视觉理论及其实现
红黑树
历史上AVL树流行的另一变种是红黑树(red black tree)。 红黑树是具有下列着色性质的二叉查找树：1、每一个节点或者红色，或者黑色。2、根是黑色的。3、如果一个节点是红色的，那么它的子节点必须是黑色的。 这种情形只有X和P是红的，G是黑的，因为否则就会在插入前有两个相连的红色节点，违反了红黑树的法则。采用伸展树的术语，X、P和G可以形成一个一字形链或之字形链(两个方向中的任一个方向)。 3、自顶向下删除红黑树中的删除也可以自顶向下进行。每一行工作都归结于能够杉树一片树叶。 注意，对于红黑树带有一个儿子的节点的情形，我们不想使用这种方法进行，因为这可能在树的中部连接两个红色节点，为红黑条件的实现增加苦难。
1K10编辑于 2022-09-03 - 来自专栏用户3288143的专栏
红黑树
那么问题来了，如何在删除和插入数据的时候保证以上性质呢，红黑树的策略就是改变颜色和旋转，改变颜色很好理解，那么旋转是什么呢？ （1）把父结点变为黑色 （2）把祖父结点变为红色 （爷爷） （3）以祖父结点旋转（爷爷） 插入数据示例 假设有如下的红黑树，符合红黑树的特征 ? 现在插入数据6，颜色假设为红色，这样就不符合红黑树的特征，所以就要对其进行变换 ? 变为黑色，祖父结点15变为红色，那么再对祖父结点15进行右旋操作，同样当前结点变为祖父结点15，至此现在的红黑树已经符合特征，变换完成 可以看出变换完的红黑树结构依然稳定，所以红黑树就解决了插入和删除的问题 红黑树的应用 JDK HashMap JDK TreeMap JDK TreeSet Windows文件搜索
1.2K20发布于 2020-07-07 - 来自专栏Java架构师必看
红黑树
对红黑树的操作在最坏情形下花费 ? 时间。红黑树是具有下列着色性质的二叉查找树： 【1】每个节点或者是黑色，或者是红色。 【2】根是黑色的； 【3】每个叶子节点（NIL）是黑色。 二、红黑树的添加操作流程 ---- 【第一步】：将红黑树当作一颗二叉查找树，将节点插入。红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。 在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。 【3】对于"特性(3)"，显然不会违背了。 详细描述如下： 【第一步】：将红黑树当作一颗二叉查找树，将节点删除。这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况： 【1】被删除节点没有儿子，即为叶节点。 【第二步】：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。
96630发布于 2021-04-30 - 来自专栏ljw
红黑树
红黑树 红黑树的概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 红黑树的性质 (路径是从根到空节点,上图是11个节点) 不是红黑树 (最长路径：一黑一红相间的路径 最短：全黑路径) 1. 每个结点不是红色就是黑色 2. 红黑树的检测分为两步： 1. 检测其是否满足红黑树的性质 红黑树的删除 https://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html 红黑树与AVL树的比较 红黑树和 AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
44710编辑于 2024-10-18 - 来自专栏BanzClub
红黑树
插入 红黑树的插入操作包括二叉搜索树的插入操作（左小右大）和红黑树平衡插入操作，平衡操作主要是为了让红黑树重新满足红黑树属性。 插入操作 1、类似于二叉搜索树，按照左小右大原则，插入新元素 2、将新元素着成红色（根据红黑树的性质，着成红色，破坏的性质较少，可以更快调整平衡） 插入平衡操作 3、平衡新树 新树可能不满足红黑树的性质 ，此时破坏了性质4，将父结点、叔结点的颜色着为黑色、祖父结点着为红色，就能使其祖父之下的子树满足红黑树，将其祖父结点作为新结点，继续判断祖父以上的红黑树是否满足红黑树； ? 下面分析一下平衡删除的场景： 3.1、平衡结点是树的根结点 根据性质2，直接着为黑色，满足红黑树性质； 3.2、平衡结点是红色（红-黑），2.2情况之后 直接将其着为黑色，满足红黑树性质； 3.3、 HashMap的红黑树删除平衡算法 ?
1.1K30发布于 2019-06-15 - 来自专栏前端开发随记
红黑树
前言 ---- 红黑树顾名思义数中的节点只能是黑色或红色，是自平衡二叉树 实现思路 红黑树的规则 节点只能是红色或黑色 根节点是黑色 叶子节点都是黑色的NIL空节点 每个红色节点的两个子节点都是黑色（每个叶子节点到根节点的路径不能有两个连续的红色节点 父节点是红色，叔节点是红色，祖节点是黑色 父节点是红色，叔节点是黑色，祖节点是黑色，插入节点是左子节点 父节点是红色，叔节点是黑色，祖节点是黑色，插入节点是右子节点 变换规则 对应以上五种情况 新节点位于树的根上
65220编辑于 2022-12-15 - 来自专栏奔跑的蛙牛技术博客
红黑树-实现
package com.example.demo2; /** * 推荐一本非常详细的树<算法> 第四版java 实现。 if(x == null) return false; return x.color == Color.RED.getIsRed(); } /** * 红黑树插入分为 向单个2-结点插入键值对 1、左链接为红色 2、右链接为红色 需要旋转 * 向树底部插入新键 如果出现红色右链接需要发生左旋 * 向一颗双键树插入新键 1、新键最大 2、新健最小 3、新键介于两者之间 * 红链接需要向上传递 * @param key * @param value */ public void put(Key key Color.BLACK.getIsRed(); h.right.color = Color.BLACK.getIsRed(); } } // 结点 package com.example.demo2; // 红黑树节点数据类型
96920发布于 2019-01-29 - 来自专栏后端从入门到精通
红黑树详解
3、红色节点的两个子节点都是黑色。（从每个叶子到根的路径不会出现两个连续的红色） 4、对于每个节点，从该节点到其叶子节点构成的所有路径上黑节点个数相同。 排序二叉树：排序二叉树是有序的，特殊结构的二叉树，可以对所有节点进行检索，但是缺点是当插入的数据正好都是有序的时候，他会退化成链表。这时候时间复杂度就会增加。 平衡树二叉树（AVL）是什么呢，最重要的特性就是最坏的情况下能保证O(logN)的时间复杂度查找，不具备的话可能退化成单链表，时间复杂度会到O（N）。 1、每个节点最多只有两个子节点。 （二叉） 2、有序：每个节点的值比他左边树所有节点都大。(必须是排序的) 3、每个节点左边树的高度与右边高度不会超过1。 为什么会出现红黑树呢，为了防止在极端情况下，二叉树退化成链表导致检索效率大大降低的问题。他肯定是排序二叉树，然后在其基础上，加上了red和black，通过变色和左旋右旋来保持他的特征。
92330编辑于 2022-12-14 - 来自专栏C/C++基础
图解红黑树
记住上面的规则也不难，我们会发现黑色结点非常特殊，规则1即“非红即黑”，规则2和3即“首尾全黑”，规则4即“红子双黑”，规则5即“路径等黑”。 这些规则强制约束红黑树，使得红黑树具有如下关键特性: （1）从根到叶子的最长路径不大于最短路径的两倍，所以红黑树大致上是平衡的。 下面是一个红黑树示例： ? 2.红黑树的自平衡 再了解红黑树的基本性质后，红黑树是如何实现自平衡的呢？红黑树总是通过旋转和变色达到自平衡。 3.红黑树的查找 因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异： 1 从根结点开始查找，把根结点设置为当前结点； 2 若当前结点为空，返回 null； 3 若当前结点不为空 （3）红黑树删除总结。
81020发布于 2020-08-11 - 来自专栏南桥谈编程
红黑树（RBTree）
文章目录 红黑树概念 红黑树的性质 红黑树节点定义 红黑树的插入 情况一: cur为红，p为红，g为黑，u存在且为红 情况二: cur为红，p为红，g为黑，u不存在 情况三: cur为红，p为红，g为黑 ，u存在且为黑 插入完整代码 红黑树验证 红黑树与AVL树的比较 红黑树的应用 红黑树概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 AVL树一样，都是三叉链，需要做孩子节点和父亲节点，红黑树还需要记录每个节点的颜色，因此需要一个_col 红黑树的插入 红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步： 按照二叉搜索的树规则插入新节点 上图所示，cur节点和p节点都是红色，违反了上述性质3.解决方式：将p节点和u节点变成黑色，g节点变成红色。g可能是这棵树的子树，如果不变红，这个子树路径黑色节点的数量都+1，破坏了性质4。 AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
27210编辑于 2024-08-24
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号