2-3-4-树和红黑树有什么关系 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

红黑树(一):构建红黑树

前两篇文章谈了B-Tree和B+Tree，它们属于多路平衡树，所有叶子结点都在同一层，除了这两种平衡树，我们熟知的还有平衡二叉树和红黑树。...平衡二叉树红黑树红黑树属于平衡二叉树，但是并非严格意义上的平衡二叉树，因为平衡二叉树要求节点的左右子树高度差不超过1，而红黑树放弃了这种高度平衡，利用对结点上色的操作来保证树相对平衡，这其中原因大概是维护一个绝对平衡的二叉树代价太大...但如果插入频率小或者只有一次构建，那么平衡二叉树的查询性能还是比红黑树高。...此时红黑树构建平衡分为4种情况: 情况一:红黑树为空树，此时插入结点充当根结点，上色为黑情况二:插入结点已经存在，此时替换插入结点值即可情况三:插入结点的位置，其父结点是黑色，此时平衡未打破，插入完成...到这里就构建完成了相对于构建新增，红黑树的删除情况更为复杂，由于时间关系(这周只有一天休息加上绘图太费劲)，留到下一次分享。构建代码红黑树构建源码

2.1K4 2

红黑树和AVL树详解

Guibas和Robert Sedgewick修改为如今的“红黑树”。红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。...红黑树可以在O(log n)时间内进行查找、插入和删除操作，这里的n是树中元素的数目。...在插入或删除节点时，可能会破坏红黑树的性质，此时需要通过重新着色和旋转操作来恢复。...应用场景：在需要频繁进行插入、删除和查找操作的场景中，红黑树和AVL树都是很好的选择。...然而，由于它们各自的特性，红黑树通常更适用于那些对插入和删除操作有较高要求的场景，而AVL树则更适用于对查询性能有较高要求的场景。

4031 0

您找到你想要的搜索结果了吗？

是的

没有找到

红黑树

红黑树的介绍红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。...红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。除了具备该特性之外，红黑树还包括许多额外的信息。...红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。红黑树的特性: (1) 每个节点或者是黑色，或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。...因而，红黑树是相对是接近平衡的二叉树。...红黑树示意图如下： AVL树的介绍 https://www.cnblogs.com/skywang12345/p/3577479.html AVL树是高度平衡的而二叉树。

9970 0

红黑树

在JDK8之前其实就已经有红黑树的应用，比如TreeMap的底层就是用了红黑树的数据结构。本文主要是为了讲解JDK8中HashMap底层数据结构的铺垫。...二、红黑树RBTree 红黑树其实是基于二叉查找树的一颗平衡二叉查找树，具有以下特点：（1）结点是红色或黑色的，在hashMap实现中用boolean的true和false表示红色或黑色。...插入结点6后发现，结点6和结点7都为红色结点，所以无法满足红黑树特点五。...再经过变色后，形成最终的红黑树： ? 三、总结个人觉得红黑树是一个挺不错的思想，红黑树在BST的基础上还引入了颜色的特点，通过变色和旋转来保持红黑树的特点，保证树的平衡。...红黑树的前身其实是234树，有兴趣的小伙伴可以了解下234树，234树和红黑树的操作完全是等价的。之所以在java中使用红黑树的数据结构是因为如果直接使用234树实现会非常繁琐。

9632 0

红黑树

这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。 # 什么是红黑树红黑树的英文是 “Red-Black Tree”，简称 R-B Tree。...在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。...所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。...# 红黑树平衡调整 # 插入操作的平衡调整红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。...除此之外，其他情况都会违背红黑树的定义，于是我们就需要进行调整，调整的过程包含两种基础的操作：左右旋转和改变颜色。红黑树的平衡调整过程是一个迭代的过程。我们把正在处理的节点叫作关注节点。

6731 0

红黑树

什么是红黑树红黑树依然是一棵二分搜索树，《算法导论》中的红黑树定义如下：每个节点或者是红色的，或者是黑色的根节点是黑色的每一个叶子节点（最后的空节点）是黑色的如果一个节点是红色的，那么他的孩子节点都是黑色的...从任意一个节点到叶子节点，经过的黑色节点是一样的在学习红黑树之前，我们有必要先学习一下什么是2-3树，学习2-3树不仅对于理解红黑树有帮助，对于理解B类树，也是有巨大帮助的。...红黑树和AVL树：由于红黑树的最大高度是2logn,所以在查找时，相比于AVL树会慢一些，而红黑树的添加和删除元素比AVL树更快一些，如果只是用于查询，AVL树的性能要更高一些。 ...，就分析到这里了，下面让我们来用代码实现一个红黑树和红黑树的添加操作： public class RBTree, V> { private static...红黑树牺牲了平衡性（2logn的高度），统计性能更优（综和增删改查所有的操作）。

4691 0

红黑树

红黑树概念红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。...通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。...红黑树的性质每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的，树中没有连续的红节点对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点...插入红黑树的叔叔是关键 u存在且为红，变色继续向上处理 u不存在或存在且为黑，旋转（单旋+双旋）+变色情况一：cur为红，parent为红，grandfather为黑（固定），uncle存在且为红...变色）处理： g右单旋 p变黑，g变红说明：uncle的情况有两种如果u节点不存在，那么cur一定是新插入节点，因为如果cur不是新插入节点，则cur和p一定有个节点颜色是黑色，就不满足性质4：每条路径黑色节点的个数相同

8132 0

红黑树

下面我们会红黑树的特征、插入以及删除来分析红黑树是如何进行自平衡的。...特征想要了解红黑树如何自平衡，就必须了解红黑树的特征，因为自平衡操作都是围绕这些特征来的，一旦一个红黑树因为插入和删除节点打破了自身的特征，那么他就需要进行自平衡(变色、旋转)来使得二叉树重新满足红黑树的特征...通过上述特征，决定了红黑树的一个重要特性：从根到叶子的最长的可能路径不多于最短路径的两倍长。下图是一张红黑树示意图： ?...当我们插入节点时需要，红黑树的特征可能会遇到以下情况：性质1和性质3总是保持着。性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。...，需要我们细细揣摩，并且反复的研究，在了解红黑树的基本概念以后，我们后续会分析一下HashMap中红黑树的实现以及着手自己实现一个红黑树。

1.2K2 0

红黑树

前言红黑树的应用还是比较广泛的。比如Java8的HashMap的底层就用到了红黑树，还有TreeMap和TreeSet也用到了。下面主要以下几个方面学习一下红黑树。...1）二叉查找树BST 2）红黑树RBTree的规则、增删查 3）红黑树的Java实现。...红黑树RBTree 基于BST存在的问题，一种新的树——平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。...其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。...关于红黑树自平衡的调整，插入和删除节点的时候都涉及到很多种Case，由于篇幅原因无法展开来一一列举，有兴趣的朋友可以参考维基百科，里面讲的非常清晰。

1.1K3 1

红黑树

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。...二、树的旋转知识当在对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。...对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。...对于"特性(4)"，是有可能违背的！那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。首先来看下伪代码描述： ?...在很多底层的实现上，有大量红黑树的实现。

1K4 0

红黑树

着色法则的一个推论是：红黑树的高度最多是2log(N+1)。因此，保证查找是一种对数的操作。和通常一样，困难在于将一个新项插入到树中。通常把新项作为树叶放到树中。...这种情形只有X和P是红的，G是黑的，因为否则就会在插入前有两个相连的红色节点，违反了红黑树的法则。采用伸展树的术语，X、P和G可以形成一个一字形链或之字形链(两个方向中的任一个方向)。...在向下的过程中当我们看到一个节点X有两个红儿子的时候，我们让X成为红的而让它的两个儿子是黑的。如果X的父节点的兄弟是红的会如何？...红黑树的具体实现是复杂的，这不仅因为有大量的可能的旋转，而且还因为一些子树可能是空的，以及处理根的特殊的情况(尤其是根没有父亲)。...当我们达到一个新的节点时，我们要确信P是红色的(归纳地按照我们试图保持的这种不变性)并且X和T是黑的(因为我们不能有两个相连的红色节点)。存在两种主要的情形。首先，X有两个黑儿子。此时有三种子情况。

1K1 0

红黑树

旋转红黑树的平衡操作是通过旋转操作来实现的，分为左旋和右旋：左旋 ? ?...插入红黑树的插入操作包括二叉搜索树的插入操作（左小右大）和红黑树平衡插入操作，平衡操作主要是为了让红黑树重新满足红黑树属性。...，此时破坏了性质4，将父结点、叔结点的颜色着为黑色、祖父结点着为红色，就能使其祖父之下的子树满足红黑树，将其祖父结点作为新结点，继续判断祖父以上的红黑树是否满足红黑树； ?...-黑色，需要进行平衡操作； 2.2、删除结点有一个子结点此时删除结点只能是黑色，并且删除结点的子结点（唯一继承结点）只能是红色，此时继承结点为红-黑色，需进行平衡操作； 2.3、删除结点有两个子结点...情况3.3.2和3.3.3 ? 《算法导论-第三版》找删除平衡的代码实现 ? HashMap的红黑树删除平衡算法 ?

1.1K3 0

红黑树

【4】对于"特性(4)"，是有可能违背的！那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。...需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。...【第二步】：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。...红黑树里面的插入和删除的操作比较难理解，这时要注意记住一点：操作之前红黑树是平衡的，颜色是符合定义的。...整个红黑树的查找，插入和删除都是O(logN)的，原因就是整个红黑树的高度是logN，查找从根到叶，走过的路径是树的高度，删除和插入操作是从叶到根的，所以经过的路径都是logN。

9433 0

红黑树

前言 ---- 红黑树顾名思义数中的节点只能是黑色或红色，是自平衡二叉树实现思路红黑树的规则节点只能是红色或黑色根节点是黑色叶子节点都是黑色的NIL空节点每个红色节点的两个子节点都是黑色（每个叶子节点到根节点的路径不能有两个连续的红色节点...父节点是红色，叔节点是红色，祖节点是黑色父节点是红色，叔节点是黑色，祖节点是黑色，插入节点是左子节点父节点是红色，叔节点是黑色，祖节点是黑色，插入节点是右子节点变换规则对应以上五种情况新节点位于树的根上...，将红色变换成黑色添加俩个空子节点至插入节点将父节点和叔节点变为黑色祖节点变为红色可能出现祖节点的父节点也是红色可以递归调整颜色，如果递归调整颜色到了根节点就需要进行旋转父节点变黑，祖节点变红，

6362 0

红黑树

红黑树红黑树的概念红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。...红黑树的性质 (路径是从根到空节点,上图是11个节点) 不是红黑树 (最长路径：一黑一红相间的路径最短：全黑路径) 1. 每个结点不是红色就是黑色 2....检测其是否满足红黑树的性质红黑树的删除 https://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html 红黑树与AVL树的比较红黑树和...AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log_2 N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比...AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

3701 0

红黑树

那么问题来了，如何在删除和插入数据的时候保证以上性质呢，红黑树的策略就是改变颜色和旋转，改变颜色很好理解，那么旋转是什么呢？...（1）把父结点变为黑色（2）把祖父结点变为红色（爷爷）（3）以祖父结点旋转（爷爷）插入数据示例假设有如下的红黑树，符合红黑树的特征 ?...现在插入数据6，颜色假设为红色，这样就不符合红黑树的特征，所以就要对其进行变换 ?...变换过程如下： 1.因为父结点7和叔叔结点10都是红色，所以首先颜色变换，将父结点7和叔叔结点10变为黑色，祖父结点8变为红色，当前结点变为祖父结点8，依然不符合红黑树特征，继续变换 2.因为父结点5为红色...变为黑色，祖父结点15变为红色，那么再对祖父结点15进行右旋操作，同样当前结点变为祖父结点15，至此现在的红黑树已经符合特征，变换完成可以看出变换完的红黑树结构依然稳定，所以红黑树就解决了插入和删除的问题

1.2K2 0

DS进阶：AVL树和红黑树

二、红黑树 2.1 红黑树的概念红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。...2.3 红黑树节点的定义和将AVL树的平衡因此换成颜色 enum Colour { RED, BLACK, }; template struct RBTreeNode...2.4 红黑树的插入和旋转（重点）情况1：首先因为我们把默认节点设置为红色，所以如果被插入位置的父亲节点是黑色的话，就不需要进行调整了。...（单旋）情况5：u存在且为黑，由情况3变化而来，插入在较高子树的另一侧（双旋）总结： 2.5 红黑树旋转和插入代码实现 //旋转代码和AVL树是一样的，只不过不需要搞平衡因子 void...其他一些库在后面关于封装map和set的过程中，会再次用到红黑树的知识，因为STL底层的架子就是用的红黑树。

3011 0

玩转红黑树：手把手教你实现和理解红黑树

从第四条和第五条的性质中，我们可以总结出一个数学结论：红黑树的根节点到叶子节点的最短路径与红黑树的根节点到叶子节点的最长路径之比1:（2N-1）。...最大的问题是这个红黑树的定义不可复用，它的业务和红黑树的实现是黏在一起的，可迁移性低。为了提高通用性和灵活性，可以将红黑树的定义做成模板化，将红黑的性质封装在一起。...二、红黑树的旋转当红黑树的性质被破环时，需要触发旋转，进行调整。旋转是为了不影响其他的性质，然后更好的变色。2.1、理论知识旋转有两种方式：左旋和右旋。这两种旋转是一种互逆的过程。...总结红黑树需要理解的难点：性质、旋转、插入、删除。红黑树是一种二叉树，中序遍历绝对有序。当红黑树的性质被破环时，需要触发旋转，进行调整。旋转有两种方式：左旋和右旋。...这决定红黑树的平衡。红黑数平衡主要是平衡黑高，即任一结点到其子叶子结点的黑色结点数量相同。红黑树的插入和删除会影响红黑树的性质，需要做调整。

8770 0

手撕AVL树、红黑树，红黑树封装map、set

）每个结点不是红色就是黑色根结点必须是黑色如果一个结点是红色，则它的两个孩子结点是黑色对于每个结点，从该结点到其后代的叶子结点，均有相同数量的黑色结点每个叶子结点（这里指空节点）都是黑色以升序插入构建红黑树图片以降序插入构建红黑树图片红黑树的实现结点定义...这四种容器的共同点是使用平衡搜索树即红黑树作为底层结构，容器中的元素是一个有序的序列。...map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。...同时调用红黑树的普通迭代器时，红黑树应该如何区分上层的value是允许被修改是不许被修改呢？？？...红黑树，红黑树封装map和set的介绍就到这里拉，如果这篇文章对你有帮助的话，请给博主点赞＋收藏，感谢看官的大力支持~

1K1 0

hashmap底层1.8有红黑树，什么是红黑树？一文了解

红黑树是一种特殊的平衡二叉树满足如下几个条件： 1、结点是红色或黑色的 2、根结点始终是黑色的 3、叶子结点也都是黑色的（当红色结点无左右孩子时，补足空结点是黑色的） 4、红色结点的子结点都是黑色的...5、对任一结点，到叶子结点的所有路径，都包含相同数目的黑色结点特征：从根结点到叶子结点的最长路径，不会超过最短路径的两倍当插入新结点使红黑树失去平衡时，通过两种方式恢复平衡：旋转和变色（...红变黑黑变红）可视化网站：树结构可视化插入结点到红黑树的逻辑约定新插入的结点都设为红色的，可以简化树的平衡过程假设要插入的结点是X 父结点是P 祖父结点是G 叔父结点是U 1）X是根结点...由从红色变为黑色 G由黑色变为红色如果G是根结点再次恢复为黑色 b) 如果叔父结点U是黑色的，并且X在左侧以P为中心，向右旋转，G和U下移，此时如果P有右孩子，右孩子R移动到G的左孩子处... 将P变为黑色将G变为红色此为举例插入16的场景 c) 如果叔父结点U是黑色的，并且X在右侧先通过左旋恢复成第二种情况然后再右旋和变色以插入19举例

6893 0

点击加载更多

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭