红黑树(Red-Black Tree,RBT)是一种平衡的二叉查找树,前面的红黑树原理与实现这篇文章中详细介绍了红黑树的细节。...在Linux的内核源代码中已经给我们实现了一棵红黑树,我们可以方便地拿过来进行使用。本文将参考Linux内核的源码和文档资料,介绍Linux内核中红黑树的实现细节及使用方法。...-2.6.39.4\Documentation\rbtree.txt 结构定义 Linux内核红黑树的实现与传统的实现方式有些不同,它对针对内核对速度的需要做了优化。...,但这就是这里红黑树实现的一个巧妙的地方。...内核中的红黑树实现非常巧妙,我们可以在自己的程序中进行使用,不过要稍微进行修改具体的方法如下: 拷贝rbtree.h和rbtree.c到工程目录下。
package com.example.demo2; /** * 推荐一本非常详细的树 第四版java 实现。...*/ public class RBTree,Value> { private Node root; // 左旋:把右链接为红色的节点变成左链接红色...if(x == null) return false; return x.color == Color.RED.getIsRed(); } /** * 红黑树插入分为...向单个2-结点插入键值对 1、左链接为红色 2、右链接为红色 需要旋转 * 向树底部插入新键 如果出现红色右链接需要发生左旋 * 向一颗双键树插入新键 1、新键最大 2、新健最小...Color.BLACK.getIsRed(); h.right.color = Color.BLACK.getIsRed(); } } // 结点 package com.example.demo2; // 红黑树节点数据类型
前言 我在前面的文章中,已经详细讲解了二叉搜索树(二叉搜索树的模拟实现-CSDN博客)、AVL树(AVL树模拟实现-CSDN博客)的模拟实现,终于,我要讲解红黑树啦~~~,让我们进入正题吧 ヾ(≧▽≦*...)o 概念 红黑树也是一棵二叉搜索树,它有如下特点 1、每个节点不是红色就是黑色 (从红黑树名字就可得知) 2、根节点是黑色的 (这是检查红黑树是否正确的一个判断条件) 3、如果一个节点是红色的...,均包含相同数目的黑色节点 (这是检查红黑树是否正确的一个判断条件) 这些特点使得红黑树效率也很高,因为他们构成了一个大特点: 最长路径的节点个数 <= 2 * 最短路径的节点个数 为什么红黑树满足...,诞生了 红黑树的模拟实现 “颜色”定义 虽然红黑树有颜色,但是红色和黑色并不是真的颜色,而是用了枚举enum的知识,将字符串转化为数字(内部),因此黑色红色的定义就是一个枚举 enum COLOR {...我们进行第三步 (3) 叔叔变为黑色 如下图所示 细心的读者可能会发现:爷爷的颜色变为红色了 在红黑树这个非红即黑的树下,我们就需要对“红色”极其敏感 这里爷爷不一定是祖先,所以,我们应该注意爷爷的父亲是什么颜色
这一篇文章就来看看如何构建红黑树 对于平衡二叉树的构建,可以参考小程序中的文章(C++版)。...平衡二叉树 红黑树 红黑树属于平衡二叉树,但是并非严格意义上的平衡二叉树,因为平衡二叉树要求节点的左右子树高度差不超过1, 而红黑树放弃了这种高度平衡,利用对结点上色的操作来保证树相对平衡,这其中原因大概是维护一个绝对平衡的二叉树代价太大..., 在插入操作比较频繁的情况下,其性能上的收益并不大(HashMap采用红黑树而不是平衡二叉树的原因)。...但如果插入频率小或者只有一次构建,那么平衡二叉树的查询性能还是比红黑树高。...此时红黑树构建平衡分为4种情况: 情况一:红黑树为空树,此时插入结点充当根结点,上色为黑 情况二:插入结点已经存在,此时替换插入结点值即可 情况三:插入结点的位置,其父结点是黑色,此时平衡未打破,插入完成
红黑树算法的Java实现 红黑树算法的Java实现 红黑树 我的主页 www.csxiaoyao.com 红黑树 github: https://github.com/csxiaoyaojianxian...nil = new RedBlackTreeNode(); private RedBlackTreeNode root = new RedBlackTreeNode(); //构造空红黑树...x = x.getParent(); } //case3:w兄弟结点为黑,w的左孩子为红,右孩子为黑...else if( w.getRight().getColor() == NodeColor.Black ){ //w的左孩子设为黑...w的右孩子为红 w.setColor(x.getParent().getColor()); x.getParent().setColor(
,因此就出现了很多自平衡的二叉查找树,这些自平衡二叉查找树的查询效率都会稳定在O(logN),红黑树就是一种自平衡的二叉查找树。...下面我们会红黑树的特征、插入以及删除来分析红黑树是如何进行自平衡的。...特征 想要了解红黑树如何自平衡,就必须了解红黑树的特征,因为自平衡操作都是围绕这些特征来的,一旦一个红黑树因为插入和删除节点打破了自身的特征,那么他就需要进行自平衡(变色、旋转)来使得二叉树重新满足红黑树的特征...下图是一张红黑树示意图: ? 自平衡 红黑树进行自平衡的操作主要有两种: 变色 旋转 下面我们通过插入操作来分析一下何时进行变色,又是何时进行旋转。...,需要我们细细揣摩,并且反复的研究,在了解红黑树的基本概念以后,我们后续会分析一下HashMap中红黑树的实现以及着手自己实现一个红黑树。
前言 红黑树的应用还是比较广泛的。比如Java8的HashMap的底层就用到了红黑树,还有TreeMap和TreeSet也用到了。 下面主要以下几个方面学习一下红黑树。...1)二叉查找树BST 2)红黑树RBTree的规则、增删查 3)红黑树的Java实现。...其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂,而且插入和删除性能差,在实际环境下的应用不如红黑树。...什么情况下会破坏红黑树的规则,什么情况下不会破坏规则呢?我们举两个简单的栗子: 添加节点 1.向原红黑树插入值为14的新节点: ?...由于父节点15是黑色节点,因此这种情况并不会破坏红黑树的规则,无需做任何调整。 2.向原红黑树插入值为21的新节点: ?
红黑树概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或 Black。...通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。...红黑树的性质 每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的,则它的两个孩子结点是黑色的,树中没有连续的红节点 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点...每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 为什么满足上面的性质,红黑树就能保证:其最长路径中节点个数不会超过最短路径中节点个数的两倍?...插入 红黑树的叔叔是关键 u存在且为红,变色继续向上处理 u不存在或存在且为黑,旋转(单旋+双旋)+变色 情况一:cur为红,parent为红,grandfather为黑(固定),uncle存在且为红
红黑树也是一种平衡二叉树,红黑树应用广泛,linux内核的rbtree.c,jdk的TreeMap和HashMap等都实现了红黑树结构。写红黑树的性质前,先按照自己的思维去考虑,红黑树为什么这样定义。...设红黑树高度为h,则红黑树到叶子结点最短路径(最小高度)大于等于h/2(根据性质45可得)。红黑树的增删改查时间复杂度都是O(lgn)。 一颗含有n个结点的红黑树,最大高度为2log(n+1)。...情况二需要两次变化先变化为情况三,然后情况三再转化为符合红黑树性质的树。 六.红黑树删除操作 红黑树删除操作首先也要按照二叉搜索树的方式去删除。...这种情况和红黑树插入中的第一种情况类似,红黑树的插入只有第一种情况可能会让整个红黑树各个路径的黑结点个数加1。同样删除中的这种情况,也可能会让整个红黑树各个路径的黑结点个数减一。...七.红黑树实现 java版 package pers.pzt.seckill; public class RBTree> { //树结点定义 private
什么是红黑树 红黑树依然是一棵二分搜索树,《算法导论》中的红黑树定义如下: 每个节点或者是红色的,或者是黑色的 根节点是黑色的 每一个叶子节点(最后的空节点)是黑色的 如果一个节点是红色的,那么他的孩子节点都是黑色的...如下图所示: 红黑树与2-3树的等价性 我们在这里定义所有的红色节点都是向左倾斜的,红色节点代表与父亲节点相融合,由于我们可以通过2-3树画出一个棵红黑树: 由此可知,红黑树是保持“...红黑树和AVL树:由于红黑树的最大高度是2logn,所以在查找时,相比于AVL树会慢一些,而红黑树的添加和删除元素比AVL树更快一些,如果只是用于查询,AVL树的性能要更高一些。 ...由于我们在本文是定义的所有红色节点都是向左倾斜的,当我们新添加的红色节点在根节点的右侧时,我们需要先进行左旋转擦欧总,然后再进行染色操作,在我们左旋转的过程中并不保持红黑树的性质,如下图: 左旋转的代码实现...: 像红黑树中添加节点,就分析到这里了,下面让我们来用代码实现一个红黑树和红黑树的添加操作: public class RBTree, V> {
在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) 每个叶子节点是黑色。...关于它的特性,需要注意的是: 第一,特性(3)中的叶子节点,是只为空(NIL或null)的节点。 第二,特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。...红黑树示意图如下: AVL树的介绍 https://www.cnblogs.com/skywang12345/p/3577479.html AVL树是高度平衡的而二叉树。
这样就能让整棵树的高度相对来说低一些,相应的插入、删除、查找等操作的效率高一些。 # 什么是红黑树 红黑树的英文是 “Red-Black Tree”,简称 R-B Tree。...如果我们将红色节点从红黑树中去掉,那单纯包含黑色节点的红黑树的高度是多少呢? 红色节点删除之后,有些节点就没有父节点了,它们会直接拿这些节点的祖父节点(父节点的父节点)作为父节点。...红黑树中包含最多黑色节点的路径不会超过 log2n,所以加入红色节点之后,最长路径不会超过 2log2n,也就是说,红黑树的高度近似 2log2n。...所以,红黑树的高度只比高度平衡的 AVL 树的高度(log2n)仅仅大了一倍,在性能上,下降得并不多。这样推导出来的结果不够精确,实际上红黑树的性能更好。...# 红黑树平衡调整 # 插入操作的平衡调整 红黑树规定,插入的节点必须是红色的。而且,二叉查找树中新插入的节点都是放在叶子节点上。
对于树的旋转,能保持不变的只有原树的搜索性质,而原树的红黑性质则不能保持,在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。...少量的旋转操作使得再添加节点时,大部分节点是可以被查询/修改的(因为旋转时为了数据安全,会锁住某些节点不能被修改,而着色操作并不影响这些)。在很多底层的实现上,有大量红黑树的实现。...如果数据完全是静态的,做一个哈希表,性能可能会更好一些。 红黑树是一个更高效的检索二叉树,因此常常用来实现关联数组(“关联数组”是一种具有特殊索引方式的数组。...五、Java中的红黑树 TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员,其中 TreeMap 是 Map 接口的常用实现类,而 TreeSet...虽然 HashMap 和 HashSet 实现的接口规范不同,但 TreeSet 底层是通过 TreeMap 来实现的,因此二者的实现方式完全一样。而 TreeMap 的实现就是红黑树算法。
历史上AVL树流行的另一变种是红黑树(red black tree)。...对于红黑树的操作在最坏情形下花费O(log N)时间,而且我们将看到,(对于插入操作的)一种慎重的非递归实现可以相对容易地完成(与AVL树相比)。...2、自顶向下红黑树上滤的实现需要用一个栈或用一些父指针保存路径。我们看到,如果我们使用一个自顶向下的过程,实际上是对红黑树应用从顶向下保证S不会是红的过程,则伸展树会更有效。这个过程在概念上是容易的。...红黑树的具体实现是复杂的,这不仅因为有大量的可能的旋转,而且还因为一些子树可能是空的,以及处理根的特殊的情况(尤其是根没有父亲)。...注意,对于红黑树带有一个儿子的节点的情形,我们不想使用这种方法进行,因为这可能在树的中部连接两个红色节点,为红黑条件的实现增加苦难。
引言相信学习过编程的都或多或多或少的听说过“红黑树”,在了解红黑树之前,需要明白它是一个二叉树,那么在哪些场景/地方使用过红黑树呢?java的hash map。Linux系统的CFS公平调度算法。...一、红黑树的定义1.1、理论知识红黑树本质上是一个二叉树。红黑树在二叉树的基础上具备如下的性质:每个结点是红的或者黑的。根结点是黑的。每个叶子结点是黑的。如果一个结点是红的,则它的两个儿子都是黑的。...1.2、代码实现了解了理论,就需要代码上进行实现。定义红黑树节点结构体包含以下内容:定义一个颜色标识符。定义左子树和右子树的指针。定义执行父节点的指针。这个是为了做性质调整需要。...最大的问题是这个红黑树的定义不可复用,它的业务和红黑树的实现是黏在一起的,可迁移性低。为了提高通用性和灵活性,可以将红黑树的定义做成模板化,将红黑的性质封装在一起。...以根结点示例:小结:红黑树插入或删除节点,最多需要旋转的次数是树的高度。2.2、代码实现(1)左旋。左旋函数的实现需要带哪些形参呢?答案是头节点和旋转节点。
说起跳表,我们就不得不提另一种非常经典的数据结构——红黑树,红黑树相对于跳表来说,虽然时间复杂度都是O(log n),但是红黑树的使用场景相对更广泛一些,在早期的Linux内核中就一直存在红黑树的实现,...所以,红黑树是每一个程序员不得不会的知识点,甚至有些变态的面试官,还会让你手写红黑树的一部分实现,比如左旋、右旋、插入平衡的过程、删除平衡的过程,这些内容非常复杂,靠死记硬背往往很难彻底掌握。...彤哥也是一直在寻找一种红黑树的记忆法,总算让我找到了那么一种还算不错的方式,从红黑树的起源出发,理解红黑树的本质,再从本质出发,彻底掌握不用死记硬背的方法,最后再把它手写出来。...从本节开始,我也将把这种方法传递给你,因此,红黑树的部分,我会分成三个小节来讲解: 从红黑树的起源,到红黑树的本质 从红黑树的本质,找到不用死记硬背的方法 不靠死记硬背,手写红黑树 好了,下面我们就进入第一小节...当然了,B+树不是本节的重点,本节的重点是红黑树。 纳尼,红黑树在哪里?写了3000多字了,还没见到红黑树的影子,我尬了~ 来了来了,有意思的红黑树来了~~ 红黑树 先上一张图,请仔细体会: ?
本文将详解两种自平衡树:AVL树和红黑树并用TypeScript将其实现,欢迎各位感兴趣的开发者阅读本文。...红黑树:故名思义,即树中的节点不是红的就是黑的,它也是一个自平衡二叉树。...上面我们实现了AVL树,我们在向AVL树中插入或移除节点可能会造成旋转,所以我们需要一个包含多次插入和删除的自平衡树,红黑树是比较好的。插入或删除频率比较低,那么AVL树比红黑树更好。...实现思路 红黑树的每个节点都需要遵循以下原则: 节点不是红的就是黑的 树的根节点是黑的 所有叶节点都是黑的 如果一个节点是红的,那么它的两个子节点都是黑的 不能有两个相邻的红节点,一个红节点不能有红的父节点或子节点...,节点插入完成后判断红黑树的规则是否得到满足 重写插入节点函数,插入时保存父节点的引用,返回节点的引用验证插入后树的属性 验证红黑树属性 要验证红黑树是否还是平衡的以及满足它的所有要求,我们需要使用两个概念
前言 ---- 红黑树顾名思义数中的节点只能是黑色或红色,是自平衡二叉树 实现思路 红黑树的规则 节点只能是红色或黑色 根节点是黑色 叶子节点都是黑色的NIL空节点 每个红色节点的两个子节点都是黑色(每个叶子节点到根节点的路径不能有两个连续的红色节点...) 任意节点到叶子节点的路径包含黑色节点的数量相同 插入节点的情况 声明N代表插入节点默认红色,P代表父节点,U代表父节点的兄弟节点,G代表祖节点 根节点为空 父节点是黑色 父节点是红色,叔节点是红色,...祖节点是黑色 父节点是红色,叔节点是黑色,祖节点是黑色,插入节点是左子节点 父节点是红色,叔节点是黑色,祖节点是黑色,插入节点是右子节点 变换规则 对应以上五种情况 新节点位于树的根上,将红色变换成黑色...添加俩个空子节点至插入节点 将父节点和叔节点变为黑色祖节点变为红色 可能出现祖节点的父节点也是红色可以递归调整颜色,如果递归调整颜色到了根节点就需要进行旋转 父节点变黑,祖节点变红,对祖节点进行右旋转
对每个结点,从该结点到其所有后代叶结点的简单路劲上,均包含数目相同的黑色结点 ? 旋转 红黑树的平衡操作是通过旋转操作来实现的,分为左旋和右旋: 左旋 ? ?...插入 红黑树的插入操作包括二叉搜索树的插入操作(左小右大)和红黑树平衡插入操作,平衡操作主要是为了让红黑树重新满足红黑树属性。...插入操作 1、类似于二叉搜索树,按照左小右大原则,插入新元素 2、将新元素着成红色(根据红黑树的性质,着成红色,破坏的性质较少,可以更快调整平衡) 插入平衡操作 3、平衡新树 新树可能不满足红黑树的性质...,此时破坏了性质4,将父结点、叔结点的颜色着为黑色、祖父结点着为红色,就能使其祖父之下的子树满足红黑树,将其祖父结点作为新结点,继续判断祖父以上的红黑树是否满足红黑树; ?...《算法导论-第三版》找删除平衡的代码实现 ? HashMap的红黑树删除平衡算法 ?
领取专属 10元无门槛券
手把手带您无忧上云