在Linux的内核源代码中已经给我们实现了一棵红黑树，我们可以方便地拿过来进行使用。本文将参考Linux内核的源码和文档资料，介绍Linux内核中红黑树的实现细节及使用方法。...简介 Linux有很多地方用到了红黑树，比如高精度计时器使用红黑树树组织定时请求，EXT3文件系统也使用红黑树树来管理目录，虚拟存储管理系统也有用红黑树树进行VMAs（Virtual Memory Areas...-2.6.39.4\Documentation\rbtree.txt 结构定义 Linux内核红黑树的实现与传统的实现方式有些不同，它对针对内核对速度的需要做了优化。...Linux内核中红黑树节点的定义如下，其中rb_node是节点类型，而rb_root是仅包含一个节点指针的类，用来表示根节点。...内核中的红黑树实现非常巧妙，我们可以在自己的程序中进行使用，不过要稍微进行修改具体的方法如下： 拷贝rbtree.h和rbtree.c到工程目录下。
平衡二叉树 红黑树 红黑树属于平衡二叉树，但是并非严格意义上的平衡二叉树，因为平衡二叉树要求节点的左右子树高度差不超过1， 而红黑树放弃了这种高度平衡，利用对结点上色的操作来保证树相对平衡，这其中原因大概是维护一个绝对平衡的二叉树代价太大...， 在插入操作比较频繁的情况下，其性能上的收益并不大(HashMap采用红黑树而不是平衡二叉树的原因)。...但如果插入频率小或者只有一次构建，那么平衡二叉树的查询性能还是比红黑树高。...此时红黑树构建平衡分为4种情况: 情况一:红黑树为空树，此时插入结点充当根结点，上色为黑 情况二:插入结点已经存在，此时替换插入结点值即可 情况三:插入结点的位置，其父结点是黑色，此时平衡未打破，插入完成...到这里就构建完成了 相对于构建新增，红黑树的删除情况更为复杂，由于时间关系(这周只有一天休息加上绘图太费劲)，留到下一次分享。 构建代码 红黑树构建源码
红黑树概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。...通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。...红黑树的性质 每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的，则它的两个孩子结点是黑色的，树中没有连续的红节点 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点...每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径中节点个数的两倍？...插入 红黑树的叔叔是关键 u存在且为红，变色继续向上处理 u不存在或存在且为黑，旋转（单旋+双旋）+变色 情况一：cur为红，parent为红，grandfather为黑（固定），uncle存在且为红
前言 红黑树的应用还是比较广泛的。比如Java8的HashMap的底层就用到了红黑树，还有TreeMap和TreeSet也用到了。 下面主要以下几个方面学习一下红黑树。...1）二叉查找树BST 2）红黑树RBTree的规则、增删查 3）红黑树的Java实现。...红黑树RBTree 基于BST存在的问题，一种新的树——平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。...其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。...下图中这棵树，就是一颗典型的红黑树： ? 什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子： 添加节点 1.向原红黑树插入值为14的新节点： ?
下面我们会红黑树的特征、插入以及删除来分析红黑树是如何进行自平衡的。...特征 想要了解红黑树如何自平衡，就必须了解红黑树的特征，因为自平衡操作都是围绕这些特征来的，一旦一个红黑树因为插入和删除节点打破了自身的特征，那么他就需要进行自平衡(变色、旋转)来使得二叉树重新满足红黑树的特征...通过上述特征，决定了红黑树的一个重要特性：从根到叶子的最长的可能路径不多于最短路径的两倍长。 下图是一张红黑树示意图： ?...当我们插入节点时需要，红黑树的特征可能会遇到以下情况： 性质1和性质3总是保持着。 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。...，需要我们细细揣摩，并且反复的研究，在了解红黑树的基本概念以后，我们后续会分析一下HashMap中红黑树的实现以及着手自己实现一个红黑树。
这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。 # 什么是红黑树 红黑树的英文是 “Red-Black Tree”，简称 R-B Tree。...在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。...所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。...所以，对于有频繁的插入、删除操作的数据集合，使用 AVL 树的代价就有点高了。 红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。...# 红黑树平衡调整 # 插入操作的平衡调整 红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。
在JDK8之前其实就已经有红黑树的应用，比如TreeMap的底层就是用了红黑树的数据结构。本文主要是为了讲解JDK8中HashMap底层数据结构的铺垫。...二、红黑树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树的性能要更高一些。 ...由于我们在本文是定义的所有红色节点都是向左倾斜的，当我们新添加的红色节点在根节点的右侧时，我们需要先进行左旋转擦欧总，然后再进行染色操作，在我们左旋转的过程中并不保持红黑树的性质，如下图： 左旋转的代码实现
但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？这就引出了红黑树的5个性质： 每个结点要么是红的要么是黑的。 根结点是黑的。...对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。...三、红黑树的插入 将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过旋转和重新着色等方法来修正该树，使之重新成为一颗红黑树。...在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。 对于"特性(3)"，显然不会违背了。...在很多底层的实现上，有大量红黑树的实现。
历史上AVL树流行的另一变种是红黑树(red black tree)。...对于红黑树的操作在最坏情形下花费O(log N)时间，而且我们将看到，(对于插入操作的)一种慎重的非递归实现可以相对容易地完成(与AVL树相比)。...2、自顶向下红黑树上滤的实现需要用一个栈或用一些父指针保存路径。我们看到，如果我们使用一个自顶向下的过程，实际上是对红黑树应用从顶向下保证S不会是红的过程，则伸展树会更有效。这个过程在概念上是容易的。...在向下的过程中当我们看到一个节点X有两个红儿子的时候，我们让X成为红的而让它的两个儿子是黑的。如果X的父节点的兄弟是红的会如何？...注意，对于红黑树带有一个儿子的节点的情形，我们不想使用这种方法进行，因为这可能在树的中部连接两个红色节点，为红黑条件的实现增加苦难。
插入 红黑树的插入操作包括二叉搜索树的插入操作（左小右大）和红黑树平衡插入操作，平衡操作主要是为了让红黑树重新满足红黑树属性。...而平衡插入操作是在固定几种情况的步骤下完成，所以，红黑树插入的时间复杂度仍为O(logn)。...，此时破坏了性质4，将父结点、叔结点的颜色着为黑色、祖父结点着为红色，就能使其祖父之下的子树满足红黑树，将其祖父结点作为新结点，继续判断祖父以上的红黑树是否满足红黑树； ?...，也就是比删除结点的左子树中的结点大，比删除结点的右子树中的结点小，所以在左子树中找最大值，或者在右子树中找最小值。...下面分析一下平衡删除的场景： 3.1、平衡结点是树的根结点 根据性质2，直接着为黑色，满足红黑树性质； 3.2、平衡结点是红色（红-黑），2.2情况之后 直接将其着为黑色，满足红黑树性质； 3.3、
前言 ---- 红黑树顾名思义数中的节点只能是黑色或红色，是自平衡二叉树 实现思路 红黑树的规则 节点只能是红色或黑色 根节点是黑色 叶子节点都是黑色的NIL空节点 每个红色节点的两个子节点都是黑色（每个叶子节点到根节点的路径不能有两个连续的红色节点...父节点是红色，叔节点是红色，祖节点是黑色 父节点是红色，叔节点是黑色，祖节点是黑色，插入节点是左子节点 父节点是红色，叔节点是黑色，祖节点是黑色，插入节点是右子节点 变换规则 对应以上五种情况 新节点位于树的根上
对红黑树的操作在最坏情形下花费 ? 时间。红黑树是具有下列着色性质的二叉查找树： 【1】每个节点或者是黑色，或者是红色。 【2】根是黑色的； 【3】每个叶子节点（NIL）是黑色。...二、红黑树的添加操作流程 ---- 【第一步】：将红黑树当作一颗二叉查找树，将节点插入。红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。...在回答之前，我们需要重新温习一下红黑树的特性：将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。...在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。 【3】对于"特性(3)"，显然不会违背了。...作为平衡二叉查找树，旋转是一个必不可少的操作。通过旋转可以降低树的高度，在红黑树里面还可以转换颜色。
那么问题来了，如何在删除和插入数据的时候保证以上性质呢，红黑树的策略就是改变颜色和旋转，改变颜色很好理解，那么旋转是什么呢？...（1）把父结点变为黑色 （2）把祖父结点变为红色 （爷爷） （3）以祖父结点旋转（爷爷） 插入数据示例 假设有如下的红黑树，符合红黑树的特征 ?...现在插入数据6，颜色假设为红色，这样就不符合红黑树的特征，所以就要对其进行变换 ?...变为黑色，祖父结点15变为红色，那么再对祖父结点15进行右旋操作，同样当前结点变为祖父结点15，至此现在的红黑树已经符合特征，变换完成 可以看出变换完的红黑树结构依然稳定，所以红黑树就解决了插入和删除的问题...红黑树的应用 JDK HashMap JDK TreeMap JDK TreeSet Windows文件搜索
前情提要 红黑树是AVL树里最流行的变种，有些资料甚至说自从红黑树出来以后，AVL树就被放到博物馆里了。红黑树是否真的有那么优秀，我们一看究竟。红黑树遵循以下5点规则，需要我们理解并熟记。...正是因为作为二叉查找树的红黑树满足这些性质，才使得树的节点是相对平衡的。...即可以保证红黑树的深度是对数的，可以保证对树的查找、插入删除等操作满足对数级的时间复杂度。 下边我们将讨论红黑树最主要的两个算法，插入和删除。...而对于问题2，我们可以把当前节点涂黑就可以让树满足红黑树的性质。...情况二在最坏的情况下一直向上推最多也是树的层数log(n),这就是红黑树删除操作的性能优势。
红黑树的基本结构 ---- 红黑树(Red-black tree) 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，常用于关联数组、字典等。...---- 在介绍红黑树前先了解其等价形式 2-3 树，对后面理解红黑树的定义很有帮助。...2-3 树 -> 红黑树 ---- 对于 2-3 树 的两种结点，有不同的转换规则： 2- 结点： 直接转换成红黑树的黑节点 3- 节点： 拆开两个关键字，左关键字标红（表示红色节点与其父节点在 2 -...---- 红黑树的创建 ---- 前面提到，创建 2-3 树 的代码编写较为复杂，因此我们肯定不会先创建一棵 2- 3 树 再将其转换成红黑树。...因为我们可以很方便地创建一棵二叉树，红黑树不过是性质比普通二叉树多了些，因此在创建红黑树时只需在创建二叉树的方法的基础上多加几种操作来保证红黑树的性质不被破坏就行了。
（从每个叶子到根的路径不会出现两个连续的红色） 4、对于每个节点，从该节点到其叶子节点构成的所有路径上黑节点个数相同。 5、所有的叶子节点都是null节点，并且是黑色。...排序二叉树：排序二叉树是有序的，特殊结构的二叉树，可以对所有节点进行检索，但是缺点是当插入的数据正好都是有序的时候，他会退化成链表。这时候时间复杂度就会增加。...平衡树二叉树（AVL）是什么呢，最重要的特性就是最坏的情况下能保证O(logN)的时间复杂度查找，不具备的话可能退化成单链表，时间复杂度会到O（N）。 1、每个节点最多只有两个子节点。...（二叉） 2、有序：每个节点的值比他左边树所有节点都大。(必须是排序的) 3、每个节点左边树的高度与右边高度不会超过1。...为什么会出现红黑树呢，为了防止在极端情况下，二叉树退化成链表导致检索效率大大降低的问题。他肯定是排序二叉树，然后在其基础上，加上了red和black，通过变色和左旋右旋来保持他的特征。
1.红黑树简介 红黑树（Red Black Tree）是一种含有红黑结点并能自平衡二叉查找树，典型的用途是实现 map。 它必须满足下面规则： 规则1：每个结点要么是黑色，要么是红色。...这些规则强制约束红黑树，使得红黑树具有如下关键特性: （1）从根到叶子的最长路径不大于最短路径的两倍，所以红黑树大致上是平衡的。...下面是一个红黑树示例： ? 2.红黑树的自平衡 再了解红黑树的基本性质后，红黑树是如何实现自平衡的呢？红黑树总是通过旋转和变色达到自平衡。...这种情况下，父结点和插入的结点都是右结点，在旋转原始图2中，我们要插入结点70 规则如下：以祖父结点【左旋】，搭配【变色】。 按照规则，步骤如下： ? 红黑树插入总结： （1）无需调整。...如果删除的是左结点，则将前驱的值复制到该结点中，然后删除前驱；如果删除的是右结点，则将后继的值复制到该结点中，然后删除后继； 这相当于是一种“取巧”的方法，我们删除结点的目的是使该结点的值在红黑树上不存在
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; // 红黑树节点数据类型
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
