红黑树也是二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。...它必须满足下面性质： 性质1：每个节点要么是黑色，要么是红色。 性质2：根节点是黑色。 性质3：每个叶子节点（NIL）是黑色。 性质4：每个红色结点的两个子结点一定都是黑色。...能有这么好的查找效率得益于红黑树自平衡的特性，而这背后的付出，红黑树的插入操作功不可没～ 红黑树插入 插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。...答案是红色。理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。...插入情景1：红黑树为空树 最简单的一种情景，直接把插入结点作为根结点就行，但注意，根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。 处理：把插入结点作为根结点，并把结点设置为黑色。
红黑树也是二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。...它必须满足下面性质： 性质1：每个节点要么是黑色，要么是红色。 性质2：根节点是黑色。 性质3：每个叶子节点（NIL）是黑色。 性质4：每个红色结点的两个子结点一定都是黑色。...能有这么好的查找效率得益于红黑树自平衡的特性，而这背后的付出，红黑树的插入操作功不可没～ 红黑树插入 插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。...理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。...插入情景1：红黑树为空树 最简单的一种情景，直接把插入结点作为根结点就行，但注意，根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。 处理：把插入结点作为根结点，并把结点设置为黑色。
简介 R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉排序树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。...我们能清晰的发现，它们是对称的。无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。...这个应该很容易想明白，因为在变换操作之前，该树是红黑树，“父节点”是红色，那么“祖父节点”一定是黑色。...红黑树和二叉搜索树的删除类似，只不过加上颜色属性（这里的子节点均指非NULL节点）： 无子节点时，删除节点可能为红色或者黑色； 1.1 如果为红色，直接删除即可，不会影响黑色节点的数量； 1.2 如果为黑色...，则需要进行删除平衡的操作了； 只有一个子节点时，删除节点只能是黑色，其子节点为红色，否则无法满足红黑树的性质了。
正文 红黑树也是二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。...它必须满足下面性质： 性质1：每个节点要么是黑色，要么是红色。 性质2：根节点是黑色。 性质3：每个叶子节点（NIL）是黑色。 性质4：每个红色结点的两个子结点一定都是黑色。...能有这么好的查找效率得益于红黑树自平衡的特性，而这背后的付出，红黑树的插入操作功不可没～ 红黑树插入 插入操作包括两部分工作：一查找插入的位置；二插入后自平衡。...理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。 所有插入情景如图7所示。...插入情景1：红黑树为空树 最简单的一种情景，直接把插入结点作为根结点就行，但注意，根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。 处理：把插入结点作为根结点，并把结点设置为黑色。
相比之下，红黑树的插入和删除操作需要旋转的次数相对较少，因此在插入和删除操作频繁的情况下，红黑树可能更加高效。 这个如果大家学完这篇文章或许能更好的理解。...插入（仅仅是插入过程） 由于红黑树也是一种搜索二叉树，是在二叉搜索树的基础上加上其平衡限制条件来实现平衡。 所以红黑树插入的逻辑也根搜索二叉树一样： 那插入一下就完事了吗？...因为新节点的默认颜色是红色，因此： 如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整； 但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连续红色结点出现，此时需要对红黑树分情况来讨论...如果g是根节点，调整完成后，需要将g改为黑色。 这样它才满足是一棵红黑树。 那上面是g是根结点的情况，那如果g是一棵子树呢？...相对而言，红黑树对平衡的控制比较宽松，降低了插入删除时需要旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
阅读本文你需具备知识点： 二叉查找树 完美平衡二叉树 红黑树也是二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时...它必须满足下面性质： 每个节点要么是黑色，要么是红色。 根节点是黑色。 每个叶子节点（Nil）是黑色。 每个红色结点的两个子结点一定都是黑色。 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。...前面讲到红黑树能自平衡，它靠的是什么？有如下三种操作： 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图 3。...能有这么好的查找效率得益于红黑树自平衡的特性，而这背后的付出，红黑树的插入操作功不可没。 红黑树插入 插入操作包括两部分工作：一是查找插入的位置；二是插入后自平衡。...理由很简单，红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。 但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多 1，必须做自平衡。
前言 有人说设计出AVL树的的人是个大牛，那写红黑树（RBTree）的人就是天才！...红黑树，是一种自平衡的二叉查找树，它的性质比较复杂，但却非常重要，常用于C++中的STL库中的set、map等容器。红黑树的节点有两种颜色：红色（red）和黑色（black）。...它具有如下五个性质： 每个节点是红色或者黑色的。 根节点是黑色的。 每个叶子节点（这里特指最下面的空节点）是黑色的。 如果一个节点是红色的，则它的子节点必须是黑色的。...在结点类中我们提到，在创建的新节点我们给与了默认颜色为RED（红色），而红黑树的根节点必须是BLACK（黑色）的，这里一定要记得修改一下颜色。...这里我将当前结点的父亲（parent）的兄弟称为叔叔结点。 示例： 当我们新增一个结点时，默认新节点的颜色为RED，如果它的父亲结点是黑色的，则不需要做任何调整，直接插入成功！
因此，“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。 红黑树的基本操作(一) 左旋和右旋 红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？...我们能清晰的发现，它们是对称的。无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。 ?...那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！ 第二步：将插入的节点着色为"红色"。 为什么着色成红色，而不是黑色呢？为什么呢？...在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。 对于"特性(3)"，显然不会违背了。...x是“黑+黑”节点，我们将x由“黑+黑”节点 变成 “黑”节点，多余的一个“黑”属性移到x的父节点中，即x的父节点多出了一个黑属性(若x的父节点原先是“黑”，则此时变成了“黑+黑”；若x的父节点原先时“
但是一般情况下，在执行添加、删除节点时，AVL树比红黑树执行的操作更多一些，效率更低一些；而且红黑树也是相对平衡的二叉树(从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点)。...因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。 3.4 添加操作 向一颗含有n个节点的红黑树中插入一个节点，可以在时间O(lgn)内完成。 将节点z插入红黑树T内。...需要执行的操作依次时：首先，将T当作一颗二叉树，将z插入；然后，将z着色为红色；最后，通过RB-INSERT-FIXUP来对节点重新着色并旋转，以此来保证删除节点后的树仍然是一颗红黑树。...在介绍为什么将则着色为红色之前，我们重新温习一下红黑树的特性： （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶子节点（NIL）是黑色。...情况二：被插入的节点的父节点是黑色。 什么也不需要做。节点被插入后，仍然是红黑树。 情况三：被插入的节点的父节点是红色。 那么，该情况与红黑树的“特性(5)”相冲突。
树是天才设计，那么 红黑树 就是 天才中的天才设计，不同于 AVL 树的极度自律，红黑树 只在条件符合时，才会进行 旋转降高度，因为旋转也是需要耗费时间的 红黑树在减少旋转次数时，在整体性能上仍然没有落后...AVL 树太多 先来一睹 红黑树 的样貌 注：红黑树在极限场景下，与 AVL 树的性能差不超过 2 倍 1.1、红黑树的定义 红黑树 也是 三叉链 结构，不过它没有 平衡因子，取而代之的是 颜色...如果一个节点是 红色 的，那么它的两个孩子节点都不能是 黑色 的（不能出现连续的红节点） 对于每个节点，从该节点到其所有后代的 NIF 节点的简单路径上，都包含相同数目的黑色节点（每条路径上都有相同数目的...红黑树 的插入操作时，也需要借助 抽象图，此时的 抽象图 不再代表高度，而是代表 黑色节点 的数量 抽象图中关注的是 黑色节点 的数量 2.2、插入流程 红黑树 的插入流程也和 二叉搜索树 基本一致...逻辑与 AVL 树一致，这里额外分享一个 DeBug 技巧： 当 随机插入 数据出错时，可以借助文件读写操作，将出错的数据保存下来，然后再次输入，反复进行调试，即可找出 Bug 因为是 随机插入 时出现的问题
同样是自平衡的二叉搜索树的AVL树，由于保持了严格的均衡策略，导致在插入和删除频繁时，性能会下降的比较厉害，而红黑树则是不强调严格的均衡性，所以在删除和插入的时候，综合性能要高于AVL树，但查询性能则略低于...红黑树的性质 红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。...第二个问题是为什么新加入的节点必须是红色的，因为从性质5上来看，要保持相等黑色节点数量才能符合红黑树的性质，如果插入的节点默认是黑色的，那么一定会破坏红黑树的性质，而红色则不一定，除非它的父节点也是红色...红黑树的平衡原理 不同于AVL树在每一个节点上维持了高度字段辅以旋转策略来维持平衡，红黑树在插入和删除的时候，维持平衡的手段主要是：变色+旋转 （一）插入操作 在红黑树上进行插入操作和删除操作会导致不再匹配红黑树的性质...情况一：只需要变色维持红黑树的性质 考虑这样一种情况，新插入节点的父节点不是黑色节点，也不是root节点，并且它的叔叔节点是红色，如下图： ?
1 红黑树 红黑树是一种特殊的二叉树，它遵循一套独特的规则： ⚠️每个节点要么是红色，要么是黑色。 ⚠️根节点必须是黑色的。 ⚠️如果一个节点是红色的，则它的两个子节点必须是黑色的。...红黑树的应用场景十分广泛，其中之一是在很多高性能的C++ STL库中被广泛采用，比如map和set。...之后我们将来实现map与set的封装！！！ 红黑树的平衡性质使其在数据库系统中也得到了广泛的应用，特别是在实现索引结构时。...这个是红黑树最为关键的规则，插入一个黑色节点，红黑树立刻就不是红黑树了！！！...是有可能违反的： 如果父节点是黑色，插入一个红色节点刚刚好，没有破坏红黑树的规则！！！ 如果父节点是红色，插入一个红色节点就违反了规则3。
但如果认真阅读了这篇的博客，并且你有 AVL 树的基础的话 (重点是 AVL 树的旋转)，其实你会发现，红黑树难只是指红黑树比较抽象，但它的逻辑其实是比 AVL 树要简单的，并且红黑树的代码也不难写。...红黑树的性质 红黑树有如下性质： 每个结点不是红色就是黑色； 根节点是黑色的； 如果一个节点是红色的，则它的两个孩子结点是黑色的 – 不允许出现连续的红色节点； 对于每个结点，从该结点到其所有后代叶结点的简单路径上...---- 三、红黑树的插入 红黑树插入的前面部分很简单，就是一般二叉搜索树的插入逻辑，需要注意的是如果插入的节点是根节点，则我们需要将节点的颜色改为黑色，因为新增节点默认是被初始化为红色的； 红黑树插入的难点在于检测插入后红黑树的性质是否被破坏...红黑树的旋转 – 和 AVL 树一样，红黑树会根据父节点位置的不同和插入节点位置的不同选择不同的旋转方式来进行调整，旋转一共分为四类： 右单旋 – 父节点在祖父节点的左侧，cur 在父节点的左侧； 左单旋...O(logN) 这个量级； 不过也正是由于红黑树不要求左右子树绝对平衡，所以红黑树相较于 AVL 树在插入和删除时的旋转次数要少一些，所以在经常进行增删的结构中红黑树的性能比 AVL 树更优，而且红黑树实现比较简单
④ 继续添加节点 18 ，自己能脑补下该怎么添加吗？...2-3 树的时间复杂度是Ologn，实际上红黑树就是由 2-3 树推导出来的，2-3 树和红黑树的关系是：2-3 树的插入和删除过程也可以对应到红黑树的旋转与颜色变换过程（至于红黑树的旋转和变色在红黑树中会重点讨论...6、红黑树 上面为什么不常见的 2-3 树说了那么多？因为 2-3树的插入和删除过程也可以对应到红黑树的旋转与颜色变换过程。下面我们先来了解下什么叫红黑树 # 红黑树的定义（特性） 1....如果新插入的节点是【黑色】，那不管是在插入到那里，一定会破坏黑色完美平衡的，因为任意一个节点的路径到叶子节点的黑色节点的数量肯定不一样了（第 6 点我自己加的，实际特性的定义是前 5 个） 红黑树的最大高度是...因为这个树本来就是黑色完美平衡了，再新插入一个新的节点红色节点，并不会破坏树的平衡以及红黑树的特性（不要去研究为什么。
与 AVL 树相比，其通过牺牲查询效率来提升插入、删除效率。 红黑树是在二叉查找树的基础上演化进来的，除了二叉查找树的要求之外，红黑树还具有如下五个强制要求（属性）： 性质 1. 结点是红色或黑色。...根据性质 5 所有最长的路径都有相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍长。 当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。...为了保持红黑树的性质，我们可以对相关结点做一系列的调整，通过对树进行旋转（例如左旋和右旋操作），即修改树中某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的五个性质...性质 1 规定红黑树节点的颜色要么是红色要么是黑色，那么在插入新节点时，这个节点应该是红色还是黑色呢？ 答案是红色，原因也不难理解。...其通过牺牲部分查询效率，提升了插入、删除效率，使其在最坏情况下也能实现 O (log N) 的时间复杂度。接着我们深入介绍了红黑树的旋转操纵，揭示了红黑树是如何实现平衡操作的。
1.2 红黑树的性质 每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的，则它的两个孩子结点是黑色的 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 每个叶子结点都是黑色的...思考： 为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？ 就上面的这颗红黑树来说，有11条路径（需算到空）我们只观察黑色结点，发现是接近满二叉树的。...虽不如AVL的极度平衡，但红黑树明显在插入节点时显得张弛有力。对于AVL来说，说是过刚易折也不为过，往往像红黑树那样增加一定的柔韧性，才是最后的选择。...即： 如果一个节点是红色的，则它的两个孩子结点是黑色的 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 如果我们新插入的结点的颜色为黑的话，插入之后一定会打破上述第二个结构...插入节点的颜色必须为红 ---- 检测新节点插入后，红黑树的性质是否造到破坏 因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时
对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。...在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。 对于"特性(3)"，显然不会违背了。...这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。...但是当叔叔节点为黑色时，则要考虑节点是左孩子还是右孩子。 ? case2很简单，通过旋转生成右边的图，而右边的情况就是case3。 总之case2就是通过一次旋转，然后进行case3的判断 3....少量的旋转操作使得再添加节点时，大部分节点是可以被查询/修改的（因为旋转时为了数据安全，会锁住某些节点不能被修改，而着色操作并不影响这些）。在很多底层的实现上，有大量红黑树的实现。
+旋转来进行调整 情况一：插入之后不破坏规则，不需要旋转，也不需要变色： 我们来看下面这种情况 当我们插入值为【66】的节点时，红黑树变成了这样 ?...可以看到插入之后红黑树的特性并未被破坏原树的特性。 那么不妨考虑一下为什么？？？？...其实也不难，第一种情况是插入红色，它爸爸是黑色，不破坏黑色节点树也没有连续红色，所以不用操作；第二种是插入红色，它爸爸是红色，而且它叔叔也是红色，所以它爸爸和它叔叔会一起变色，它爷爷会随之变色，所以能够达到同一层红色统一变黑色...若新插入节点的爸爸是黑色节点，红黑树不需要调整 3. 若新插入节点的爸爸和它叔叔都是红色节点，红黑树只需要变色，不需要旋转 4....若新插入节点的爸爸是红色，但是它叔叔是黑色（可能为null，但是null是叶子节点，正儿八经的黑色），这时，一定是变色+旋转。
红-黑树的特征 它主要有两个特征： 1.节点都有颜色；2.在插入和删除的过程中，要遵循保持这些颜色的不同排列的规则。...在红-黑树中插入的节点都是红色的，这不是偶然的，因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能性更小。...3.1 红-黑树的节点 红-黑树是对二叉搜索树的改进，所以其节点与二叉搜索树是差不多的，只不过在它基础上增加了一个boolean型变量来表示节点的颜色，具体看RBNode类： public class...如果是第一次插入，由于原树为空，所以只会违反红-黑树的规则2，所以只要把根节点涂黑即可；如果插入节点的父节点是黑色的，那不会违背红-黑树的规则，什么也不需要做；但是遇到如下三种情况时，我们就要开始变色和旋转了...于情况3：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。我们要做的操作有：将当前节点的父节点(7)涂黑，将祖父节点(11)涂红，在祖父节点为支点做右旋操作。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
