首页
学习
活动
专区
工具
TVP
发布

linux内核数据结构

(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是仅包含一个节点指针的类,用来表示根节点。

1.2K40

(二):删除操作

上一篇文章根据的定义实现了的插入操作,在节点插入操作过程中,我们默认插入节点为,然后判断是否需要进行平衡操作,那么今天就来看一下删除操作需要考虑哪些情况。...删除操作比插入操作要更为复杂,因为需要考虑的因素比节点插入要多。...情况2.2:然后我们考虑黑色,这种情况较为复杂,因为黑色节点被删除之后,会失去平衡,此时需要调整平衡。...1.1> 左孩子存在(不为Nil),需要两次调整实现平衡 ?...到这里删除节点的操作就完成了,对于文章有疑问,可通过公众号回复加群来一起探讨。 完整源码查看: 源码

1.3K32
您找到你想要的搜索结果了吗?
是的
没有找到

(一):构建

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

1.6K42

Python实现删除操作

上一篇文章使用Python实现了的插入操作。参考:Python实现的插入操作 本篇文章使用Python实现删除操作。 先将的5条特性列出来: 1. 节点是红色或黑色。...二、实现删除方法 删除方法可以分两个步骤实现,第一步是按照二叉搜索的方法将节点删除,第二步是对删除节点后的进行调整,使重新满足5条特性。...1.1 被删除节点是节点,直接将节点删除,不会破坏的5条特性,不需要进行调整。 1.2 被删除节点是节点。这是删除中最复杂的部分,具体有如下三种情况。 1.2.1 被删除节点是根节点。..._rb_delete(rear_node) 删除节点,首先这个节点要在中,因此不能创建一个节点然后删除,而是根据节点的值,先到中进行搜索,如果这个值存在中,则将其删除。...删除节点66后的结构如下图。 ? 可以看到,删除功能已经实现了。

83430

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

81431

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

43220

下面我们会红的特征、插入以及删除来分析是如何进行自平衡的。...特征 想要了解如何自平衡,就必须了解的特征,因为自平衡操作都是围绕这些特征来的,一旦一个因为插入和删除节点打破了自身的特征,那么他就需要进行自平衡(变色、旋转)来使得二叉重新满足的特征...通过上述特征,决定了的一个重要特性:从根到叶子的最长的可能路径不多于最短路径的两倍长。 下图是一张示意图: ?...是一种自平衡的二叉查找,因此删除节点的时候符合删除二叉查找树节点的规律,假设删除的节点为N,那么我们需要找到N节点左子树下面最大的节点或者找到右子树中最小的节点M,然后用M的值替换N的值(注意这里只拷贝值...,需要我们细细揣摩,并且反复的研究,在了解的基本概念以后,我们后续会分析一下HashMap中的实现以及着手自己实现一个

89420

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

70000

什么是 依然是一棵二分搜索,《算法导论》中的定义如下: 每个节点或者是红色的,或者是黑色的 根节点是黑色的 每一个叶子节点(最后的空节点)是黑色的 如果一个节点是红色的,那么他的孩子节点都是黑色的...从任意一个节点到叶子节点,经过的黑色节点是一样的   在学习之前,我们有必要先学习一下什么是2-3,学习2-3不仅对于理解有帮助,对于理解B类,也是有巨大帮助的。...如下图所示: 与2-3的等价性   我们在这里定义所有的红色节点都是向左倾斜的,红色节点代表与父亲节点相融合,由于我们可以通过2-3画出一个棵:   由此可知,是保持“...和AVL:由于的最大高度是2logn,所以在查找时,相比于AVL会慢一些,而的添加和删除元素比AVL更快一些,如果只是用于查询,AVL的性能要更高一些。   ...向中添加一个新元素,类比于2-3中添加一个新元素,就是或者添加进2-节点,形成3-节点;或者添加进3-节点,暂时形成一个4-节点,这样我们可以让我们的,永远添加节点。

10910

这样就能让整棵的高度相对来说低一些,相应的插入、删除、查找等操作的效率高一些。 # 什么是 的英文是 “Red-Black Tree”,简称 R-B Tree。...如果我们将红色节点从中去掉,那单纯包含黑色节点的的高度是多少呢? 红色节点删除之后,有些节点就没有父节点了,它们会直接拿这些节点的祖父节点(父节点的父节点)作为父节点。...# 为什么需要 AVL 是一种高度平衡的二叉,所以查找的效率非常高,但是,有利就有弊,AVL 为了维持这种高度的平衡,就要付出更多的代价。每次插入、删除都要做调整,就比较复杂、耗时。...所以,对于有频繁的插入、删除操作的数据集合,使用 AVL 的代价就有点高了。 只是做到了近似平衡,并不是严格的平衡,所以在维护平衡的成本上,要比 AVL 要低。...所以,的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说,要面对各种异常情况,为了支撑这种工业级的应用,我们更倾向于这种性能稳定的平衡二叉查找

35310

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

68420

虽然本质上是一棵二叉查找,但它在二叉查找的基础上增加了着色和相关的性质使得相对平衡,从而保证了的查找、插入、删除的时间复杂度最坏为O(log n)。...正是的这5条性质,使一棵n个结点的始终保持了logn的高度(的高度至多为2log(n+1)证明略),从而也就解释了上面所说的“的查找、插入、删除的时间复杂度最坏为O(log n)...二、的旋转知识 当在对红进行插入和删除等操作时,对做了修改可能会破坏的性质。...对于的旋转,能保持不变的只有原的搜索性质,而原性质则不能保持,在的数据插入和删除后可利用旋转和颜色重涂来恢复性质。...所以的选择操作很少。局部至多2次(插入最多两次旋转,删除最多三次旋转)。大部分都是着色操作。

72740

历史上AVL流行的另一变种是(red black tree)。...这种情形只有X和P是的,G是的,因为否则就会在插入前有两个相连的红色节点,违反了的法则。采用伸展的术语,X、P和G可以形成一个一字形链或之字形链(两个方向中的任一个方向)。...2、自顶向下树上滤的实现需要用一个栈或用一些父指针保存路径。我们看到,如果我们使用一个自顶向下的过程,实际上是对红应用从顶向下保证S不会是的过程,则伸展会更有效。这个过程在概念上是容易的。...3、自顶向下删除中的删除也可以自顶向下进行。每一行工作都归结于能够杉树一片树叶。...注意,对于带有一个儿子的节点的情形,我们不想使用这种方法进行,因为这可能在的中部连接两个红色节点,为条件的实现增加苦难。

71610

那么问题来了,如何在删除和插入数据的时候保证以上性质呢,的策略就是改变颜色和旋转,改变颜色很好理解,那么旋转是什么呢?...(1)把父结点变为黑色 (2)把祖父结点变为红色 (爷爷) (3)以祖父结点旋转(爷爷) 插入数据示例 假设有如下的,符合的特征 ?...现在插入数据6,颜色假设为红色,这样就不符合的特征,所以就要对其进行变换 ?...变为黑色,祖父结点15变为红色,那么再对祖父结点15进行右旋操作,同样当前结点变为祖父结点15,至此现在的已经符合特征,变换完成 可以看出变换完的树结构依然稳定,所以就解决了插入和删除的问题...的应用 JDK HashMap JDK TreeMap JDK TreeSet Windows文件搜索

91820

---- 将内的某一个节点删除。...需要执行的操作依次是:首先,将当作一颗二叉查找,将该节点从二叉查找删除;然后,通过"旋转和重新着色"等一系列来修正该,使之重新成为一棵。...因为"第一步"中删除节点之后,可能会违背的特性。所以需要通过"旋转和重新着色"来修正该,使之重新成为一棵。...里面的插入和删除的操作比较难理解,这时要注意记住一点:操作之前是平衡的,颜色是符合定义的。...整个的查找,插入和删除都是O(logN)的,原因就是整个的高度是logN,查找从根到叶,走过的路径是的高度,删除和插入操作是从叶到根的,所以经过的路径都是logN。

64830

插入 的插入操作包括二叉搜索的插入操作(左小右大)和平衡插入操作,平衡操作主要是为了让重新满足属性。...删除 删除操作同样需要两个步骤:二叉删除操作和删除平衡操作。...下面分析一下删除结点的场景(相比于二叉,增加的属性,需要考虑颜色的平衡性): 2.1、删除结点无子结点(只有叶结点-Nil结点) 如果结点是红色,直接删除即可,将删除结点的一个叶结点...下面分析一下平衡删除的场景: 3.1、平衡结点是的根结点 根据性质2,直接着为黑色,满足性质; 3.2、平衡结点是红色(-),2.2情况之后 直接将其着为黑色,满足性质; 3.3、...《算法导论-第三版》找删除平衡的代码实现 ? HashMap的删除平衡算法 ?

86730

一篇文章搞懂的原理及实现2-3-4 Tree(2-3-4)左倾删除操作删除最小节点删除任意节点总结

但我们在此只考虑左倾的情况,所以这种树也叫做左倾 这样,对于任何一棵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的表示。接着介绍插入和删除算法。

4.2K31

图解

的基本结构 ---- (Red-black tree) 是一种自平衡二叉查找,是在计算机科学中用到的一种数据结构,常用于关联数组、字典等。...---- 在介绍树前先了解其等价形式 2-3 ,对后面理解的定义很有帮助。...2-3 -> ---- 对于 2-3 的两种结点,有不同的转换规则: 2- 结点: 直接转换成节点 3- 节点: 拆开两个关键字,左关键字标(表示红色节点与其父节点在 2 -...---- 的创建 ----   前面提到,创建 2-3 的代码编写较为复杂,因此我们肯定不会先创建一棵 2- 3 再将其转换成。...因为我们可以很方便地创建一棵二叉不过是性质比普通二叉多了些,因此在创建时只需在创建二叉的方法的基础上多加几种操作来保证的性质不被破坏就行了。

79010

算法

前情提要 是AVL里最流行的变种,有些资料甚至说自从出来以后,AVL就被放到博物馆里了。是否真的有那么优秀,我们一看究竟。遵循以下5点规则,需要我们理解并熟记。...即可以保证的深度是对数的,可以保证对的查找、插入删除等操作满足对数级的时间复杂度。 下边我们将讨论最主要的两个算法,插入和删除。...1三种情况 删除相对复杂些,但只要我们思路明确,问题就迎刃而解。...如果待删除的实际节点是红色的,我们可以用普通方法进行删除,因为删除过后依然满足的性质。...情况二在最坏的情况下一直向上推最多也是的层数log(n),这就是删除操作的性能优势。

1.1K120

扫码

添加站长 进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

    运营活动

    活动名称
    广告关闭
    领券