红黑树（Red-Black Tree，RBT）是一种平衡的二叉查找树，前面的红黑树原理与实现这篇文章中详细介绍了红黑树的细节。...在Linux的内核源代码中已经给我们实现了一棵红黑树，我们可以方便地拿过来进行使用。本文将参考Linux内核的源码和文档资料，介绍Linux内核中红黑树的实现细节及使用方法。...简介 Linux有很多地方用到了红黑树，比如高精度计时器使用红黑树树组织定时请求，EXT3文件系统也使用红黑树树来管理目录，虚拟存储管理系统也有用红黑树树进行VMAs（Virtual Memory Areas...-2.6.39.4\Documentation\rbtree.txt 结构定义 Linux内核红黑树的实现与传统的实现方式有些不同，它对针对内核对速度的需要做了优化。...Linux内核中红黑树节点的定义如下，其中rb_node是节点类型，而rb_root是仅包含一个节点指针的类，用来表示根节点。
上一篇文章根据红黑树的定义实现了红黑树的插入操作，在节点插入操作过程中，我们默认插入节点为红，然后判断是否需要进行平衡操作，那么今天就来看一下红黑树的删除操作需要考虑哪些情况。...红黑树的删除操作比插入操作要更为复杂，因为需要考虑的因素比节点插入要多。...情况2.2：然后我们考虑黑色，这种情况较为复杂，因为黑色节点被删除之后，红黑树会失去平衡，此时需要调整平衡。...1.1> 左孩子存在(不为Nil)，需要两次调整实现红黑树平衡 ?...到这里删除节点的操作就完成了，对于文章有疑问，可通过公众号回复加群来一起探讨。 完整源码查看: 红黑树源码
这一篇文章就来看看如何构建红黑树 对于平衡二叉树的构建，可以参考小程序中的文章(C++版)。...平衡二叉树 红黑树 红黑树属于平衡二叉树，但是并非严格意义上的平衡二叉树，因为平衡二叉树要求节点的左右子树高度差不超过1， 而红黑树放弃了这种高度平衡，利用对结点上色的操作来保证树相对平衡，这其中原因大概是维护一个绝对平衡的二叉树代价太大...但如果插入频率小或者只有一次构建，那么平衡二叉树的查询性能还是比红黑树高。...此时红黑树构建平衡分为4种情况: 情况一:红黑树为空树，此时插入结点充当根结点，上色为黑 情况二:插入结点已经存在，此时替换插入结点值即可 情况三:插入结点的位置，其父结点是黑色，此时平衡未打破，插入完成...到这里就构建完成了 相对于构建新增，红黑树的删除情况更为复杂，由于时间关系(这周只有一天休息加上绘图太费劲)，留到下一次分享。 构建代码 红黑树构建源码
上一篇文章使用Python实现了红黑树的插入操作。参考：Python实现红黑树的插入操作 本篇文章使用Python实现红黑树的删除操作。 先将红黑树的5条特性列出来： 1. 节点是红色或黑色。...二、实现红黑树的删除方法 红黑树的删除方法可以分两个步骤实现，第一步是按照二叉搜索树的方法将节点删除，第二步是对删除节点后的红黑树进行调整，使红黑树重新满足5条特性。...1.1 被删除节点是红节点，直接将节点删除，不会破坏红黑树的5条特性，不需要进行调整。 1.2 被删除节点是黑节点。这是红黑树删除中最复杂的部分，具体有如下三种情况。 1.2.1 被删除节点是根节点。..._rb_delete(rear_node) 删除节点，首先这个节点要在红黑树中，因此不能创建一个节点然后删除，而是根据节点的值，先到红黑树中进行搜索，如果这个值存在红黑树中，则将其删除。...删除节点66后红黑树的结构如下图。 ? 可以看到，红黑树的删除功能已经实现了。
红黑树概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。...通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。...红黑树的性质 每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的，则它的两个孩子结点是黑色的，树中没有连续的红节点 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点...每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径中节点个数的两倍？...插入 红黑树的叔叔是关键 u存在且为红，变色继续向上处理 u不存在或存在且为黑，旋转（单旋+双旋）+变色 情况一：cur为红，parent为红，grandfather为黑（固定），uncle存在且为红
下面我们会红黑树的特征、插入以及删除来分析红黑树是如何进行自平衡的。...特征 想要了解红黑树如何自平衡，就必须了解红黑树的特征，因为自平衡操作都是围绕这些特征来的，一旦一个红黑树因为插入和删除节点打破了自身的特征，那么他就需要进行自平衡(变色、旋转)来使得二叉树重新满足红黑树的特征...通过上述特征，决定了红黑树的一个重要特性：从根到叶子的最长的可能路径不多于最短路径的两倍长。 下图是一张红黑树示意图： ?...红黑树是一种自平衡的二叉查找树，因此删除节点的时候符合删除二叉查找树节点的规律，假设删除的节点为N，那么我们需要找到N节点左子树下面最大的节点或者找到右子树中最小的节点M，然后用M的值替换N的值(注意这里只拷贝值...，需要我们细细揣摩，并且反复的研究，在了解红黑树的基本概念以后，我们后续会分析一下HashMap中红黑树的实现以及着手自己实现一个红黑树。
前言 红黑树的应用还是比较广泛的。比如Java8的HashMap的底层就用到了红黑树，还有TreeMap和TreeSet也用到了。 下面主要以下几个方面学习一下红黑树。...1）二叉查找树BST 2）红黑树RBTree的规则、增删查 3）红黑树的Java实现。...红黑树RBTree 基于BST存在的问题，一种新的树——平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。...其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。...关于红黑树自平衡的调整，插入和删除节点的时候都涉及到很多种Case，由于篇幅原因无法展开来一一列举，有兴趣的朋友可以参考维基百科，里面讲的非常清晰。
在JDK8之前其实就已经有红黑树的应用，比如TreeMap的底层就是用了红黑树的数据结构。本文主要是为了讲解JDK8中HashMap底层数据结构的铺垫。...一、二叉查找树BST 红黑树的本质就是一颗二叉查找树，二叉查找树的特点如下： （1）左节点的值都小于或等于其父类（父类或根节点）的值。...二、红黑树RBTree 红黑树其实是基于二叉查找树的一颗平衡二叉查找树，具有以下特点： （1）结点是红色或黑色的，在hashMap实现中用boolean的true和false表示红色或黑色。...再经过变色后，形成最终的红黑树： ? 三、总结 个人觉得红黑树是一个挺不错的思想，红黑树在BST的基础上还引入了颜色的特点，通过变色和旋转来保持红黑树的特点，保证树的平衡。...红黑树的前身其实是234树，有兴趣的小伙伴可以了解下234树，234树和红黑树的操作完全是等价的。之所以在java中使用红黑树的数据结构是因为如果直接使用234树实现会非常繁琐。
红黑树的介绍 红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。...红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。 除了具备该特性之外，红黑树还包括许多额外的信息。...红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。 红黑树的特性: (1) 每个节点或者是黑色，或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。...因而，红黑树是相对是接近平衡的二叉树。...红黑树示意图如下： AVL树的介绍 https://www.cnblogs.com/skywang12345/p/3577479.html AVL树是高度平衡的而二叉树。
什么是红黑树 红黑树依然是一棵二分搜索树，《算法导论》中的红黑树定义如下： 每个节点或者是红色的，或者是黑色的 根节点是黑色的 每一个叶子节点（最后的空节点）是黑色的 如果一个节点是红色的，那么他的孩子节点都是黑色的...从任意一个节点到叶子节点，经过的黑色节点是一样的 在学习红黑树之前，我们有必要先学习一下什么是2-3树，学习2-3树不仅对于理解红黑树有帮助，对于理解B类树，也是有巨大帮助的。...如下图所示： 红黑树与2-3树的等价性 我们在这里定义所有的红色节点都是向左倾斜的，红色节点代表与父亲节点相融合，由于我们可以通过2-3树画出一个棵红黑树： 由此可知，红黑树是保持“...红黑树和AVL树：由于红黑树的最大高度是2logn,所以在查找时，相比于AVL树会慢一些，而红黑树的添加和删除元素比AVL树更快一些，如果只是用于查询，AVL树的性能要更高一些。 ...向红黑树中添加一个新元素，类比于2-3树中添加一个新元素，就是或者添加进2-节点，形成3-节点；或者添加进3-节点，暂时形成一个4-节点，这样我们可以让我们的红黑树，永远添加红节点。
这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。 # 什么是红黑树 红黑树的英文是 “Red-Black Tree”，简称 R-B Tree。...如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？ 红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。...# 为什么需要红黑树 AVL 树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入、删除都要做调整，就比较复杂、耗时。...所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。 红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。...所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。
红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。...正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度（红黑树的高度至多为2log(n+1)证明略），从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)...二、树的旋转知识 当在对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。...对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。...所以红黑树的选择操作很少。局部至多2次（插入最多两次旋转，删除最多三次旋转）。大部分都是着色操作。
历史上AVL树流行的另一变种是红黑树(red black tree)。...这种情形只有X和P是红的，G是黑的，因为否则就会在插入前有两个相连的红色节点，违反了红黑树的法则。采用伸展树的术语，X、P和G可以形成一个一字形链或之字形链(两个方向中的任一个方向)。...2、自顶向下红黑树上滤的实现需要用一个栈或用一些父指针保存路径。我们看到，如果我们使用一个自顶向下的过程，实际上是对红黑树应用从顶向下保证S不会是红的过程，则伸展树会更有效。这个过程在概念上是容易的。...3、自顶向下删除红黑树中的删除也可以自顶向下进行。每一行工作都归结于能够杉树一片树叶。...注意，对于红黑树带有一个儿子的节点的情形，我们不想使用这种方法进行，因为这可能在树的中部连接两个红色节点，为红黑条件的实现增加苦难。
---- 将红黑树内的某一个节点删除。...需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。...因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。...红黑树里面的插入和删除的操作比较难理解，这时要注意记住一点：操作之前红黑树是平衡的，颜色是符合定义的。...整个红黑树的查找，插入和删除都是O(logN)的，原因就是整个红黑树的高度是logN，查找从根到叶，走过的路径是树的高度，删除和插入操作是从叶到根的，所以经过的路径都是logN。
红黑树 红黑树的概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。...红黑树的性质 (路径是从根到空节点,上图是11个节点) 不是红黑树 (最长路径：一黑一红相间的路径 最短：全黑路径) 1. 每个结点不是红色就是黑色 2....红黑树的检测分为两步： 1....检测其是否满足红黑树的性质 红黑树的删除 https://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html 红黑树与AVL树的比较 红黑树和...AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
前言 ---- 红黑树顾名思义数中的节点只能是黑色或红色，是自平衡二叉树 实现思路 红黑树的规则 节点只能是红色或黑色 根节点是黑色 叶子节点都是黑色的NIL空节点 每个红色节点的两个子节点都是黑色（每个叶子节点到根节点的路径不能有两个连续的红色节点...父节点是红色，叔节点是红色，祖节点是黑色 父节点是红色，叔节点是黑色，祖节点是黑色，插入节点是左子节点 父节点是红色，叔节点是黑色，祖节点是黑色，插入节点是右子节点 变换规则 对应以上五种情况 新节点位于树的根上
插入 红黑树的插入操作包括二叉搜索树的插入操作（左小右大）和红黑树平衡插入操作，平衡操作主要是为了让红黑树重新满足红黑树属性。...删除 红黑树的删除操作同样需要两个步骤：二叉树的删除操作和删除平衡操作。...下面分析一下红黑树删除结点的场景（相比于二叉树，增加红黑树的属性，需要考虑颜色的平衡性）： 2.1、删除结点无子结点（只有叶结点-Nil结点） 如果结点是红色，直接删除即可，将删除结点的一个叶结点...下面分析一下平衡删除的场景： 3.1、平衡结点是树的根结点 根据性质2，直接着为黑色，满足红黑树性质； 3.2、平衡结点是红色（红-黑），2.2情况之后 直接将其着为黑色，满足红黑树性质； 3.3、...《算法导论-第三版》找删除平衡的代码实现 ? HashMap的红黑树删除平衡算法 ?
那么问题来了，如何在删除和插入数据的时候保证以上性质呢，红黑树的策略就是改变颜色和旋转，改变颜色很好理解，那么旋转是什么呢？...（1）把父结点变为黑色 （2）把祖父结点变为红色 （爷爷） （3）以祖父结点旋转（爷爷） 插入数据示例 假设有如下的红黑树，符合红黑树的特征 ?...现在插入数据6，颜色假设为红色，这样就不符合红黑树的特征，所以就要对其进行变换 ?...变为黑色，祖父结点15变为红色，那么再对祖父结点15进行右旋操作，同样当前结点变为祖父结点15，至此现在的红黑树已经符合特征，变换完成 可以看出变换完的红黑树结构依然稳定，所以红黑树就解决了插入和删除的问题...红黑树的应用 JDK HashMap JDK TreeMap JDK TreeSet Windows文件搜索
但我们在此只考虑左倾的情况，所以这种树也叫做左倾红黑树 这样，对于任何一棵2-3-4树，我们都可以得到一棵唯一对应的左倾红黑树 ?...由于每次在最后都将4-node 进行color flip了，那么自然红黑树中不存在4-node了，所以就变成了2-3树的红黑树 我们可以对比普通红黑树的插入算法的实现 private Node insert...首先我们介绍一下，删除完成之后，如何调整红黑树为左倾的红黑树？...删除的当前节点不能是2-node 如果有必要可以变换成4-node 从底部删除节点 向上的fix过程中，消除4-node 红黑树的删除操作与插入操作一样，极其复杂，所以先从相对容易的情况开始考虑 删除最大节点...image.png 总结 至此，我们就基本讲完了红黑树的基本原理和实现。 我们首先从2-3-4树开始讲起，然后引出红黑树其实就是2-3-4树的BST的表示。接着介绍插入和删除算法。
文章目录 红黑树概念 红黑树的性质 红黑树节点定义 红黑树的插入 情况一: cur为红，p为红，g为黑，u存在且为红 情况二: cur为红，p为红，g为黑，u不存在 情况三: cur为红，p为红，g为黑...，u存在且为黑 插入完整代码 红黑树验证 红黑树与AVL树的比较 红黑树的应用 红黑树概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。...AVL树一样，都是三叉链，需要做孩子节点和父亲节点，红黑树还需要记录每个节点的颜色，因此需要一个_col 红黑树的插入 红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步： 按照二叉搜索的树规则插入新节点...AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。...红黑树的应用 C++ STL库 – map/set、mutil_map/mutil_set Java 库 linux内核 其他一些库
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM
