红黑树原理是什么建立过程,哪种树结构是一种自平衡二叉搜索树的方法

本文目录

• 1.哪种树结构是一种自平衡二叉搜索树的方法
• 2.红黑树在linux内核的作用
• 3.红黑树增加节点
• 4.红黑树的算法原理及讲解

哪种树结构是一种自平衡二叉搜索树的方法

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

红黑树的原理是通过进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而实现关联数组，存储有序的数据。它是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，其典型的用途就是实现关联数组。

红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树。

而由于每一颗红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。

行为特征：

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

性质1、节点是红色或黑色。

性质2、根节点是黑色。

性质3、所有叶子都是黑色。（叶子是NUIL节点）。

性质4、每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）。

性质5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树在linux内核的作用

红黑树的各种操作的时间复杂度是多少？

红黑树的操作时间跟二叉查找树的时间复杂度是一样的，执行查找、插入、删除等操作的时间复杂度为O（logn）。红黑树是特殊的AVL树，遵循红定理和黑定理红定理：不能有两个相连的红节点黑定理：根节点必须是黑节点，而且所有节点通向NULL的路径上，所经过的黑节点的个数必须相等

红黑树的算法原理及讲解？

红黑树原理和算法详细介绍

红黑树定义：

(1)每个节点或者是黑色，或者是红色。

(2)根节点是黑色。

(3)每个叶子节点是黑色。

(4)如果一个节点是红色的，则它的子节点必须是黑色的。

(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

证明

首先定义一个节点x的黑高为bh(x)bh(x)bh(x),表示从x到任意一个叶子节点路径上黑色节点的个数（不包括x）。

1.第一步，先证明以某一节点x为根的子树中至少包含2bh(x)?12^{bh(x)}?12

bh(x)?1个内节点(不是叶子的都是内节点)。用数学归纳法证明。

如果x的高度为0，那么x是叶节点，包含0个内节点，满足该式子。

对于高度为正值的x，其两个孩子至少包含2bh(x)?1?12^{bh(x)?1}?12bh(x)?1?1个内节点，

所以以x为根的子树至少包含(2bh(x)?1?1)+(2bh(x)?1?1)+1=2bh(x)?1(2^{bh(x)?1}?1)+(2^{bh(x)?1}?1)+1=2^{bh(x)}?1(2bh(x)?1?1)+(2

bh(x)?1?1)+1=2bh(x)?1个内节点。

2.第二步，对于一棵高度为h的树，任意一条从根到叶节点（不包括根）的路径上至少有一半黑色节点，从而bh(x)≥h/2bh(x)≥h/2bh(x)≥h/2，所以n≥2bh(x)?1≥2h/2?1n≥2^{bh(x)}?1≥2^{h/2}?1n≥2bh(x)?1≥2h/2?1，即h≤2log(n+1)h≤2log(n+1)h≤2log(n+1)

红黑树和链表的区别？

红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。能在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

而红链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

关于红黑树描述正确的？

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

性质1.节点是红色或黑色。

性质2.根是黑色。

性质3每个叶节点是黑色的。

性质4每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

二叉树是用来干什么的?在软件工程方面有什么用途，请帮小弟举几个实例？

用的最多的应该是平衡二叉树，有种特殊的平衡二叉树红黑树，查找、插入、删除的时间复杂度最坏为O(logn)Java集合中的TreeSet和TreeMap，C++STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。还有哈夫曼树编码方面的应用。B-Tree，B+-Tree在文件系统中的应用。如有错误或遗漏还请各位指正补充。

红黑树增加节点

在网上看了很多写红黑树的博客，大部分写的都不是很到位，有些关于红黑树的图都是有问题的，很多都没有说清楚什么情况促发哪种操作，看完之后还是不理解，在查看了很多资料之后，决定自己写关于红黑树的理解。分为添加节点篇和删除节点篇，本文为将阐述红黑树的基本原理以及在添加节点时，各种情况下对应的操作。（在看本文前，需要先了解平衡二叉树的原理，因为红黑树的有些操作和二叉平衡树类似）

红黑树之所以被称为红黑树，是因为红黑树的节点的颜色非红即黑，通过对节点颜色的限制和一系列的限制条件来确保红黑树没有任何一条路径是其他路径的两倍长。

红黑树需要满足以下条件：

（1）每个节点非黑即红。

（2）根节点是黑色。

（3）每个叶子节点，即空节点是黑的。

（4）红色节点的两个孩子节点都是黑的

（5）每个节点到子孙节点的所有路径上包含相同数量的黑色节点

如图1所示，就是一颗红黑树：

在插入节点时，总是插入红色节点，这样可以 尽量 避免破坏红黑树的结构，为什么说插入红节点可以 尽量 避免破坏红黑树的结构，假如现在要插入6，即插入到12节点的左孩子，如果6节点是黑色的，那么就会破坏规则（5），即图2中绿色路径上的黑色节点的数量比黄色路径上黑色节点的数量多，如果6节点是红色的，则不会破坏树结构，如图3所示。

红黑树节点的添加可分为以下3种情况

分析：因为插入的是红色节点，所以违背规则（2）根节点是黑色

解决方案：只需要把这个节点的颜色改成黑色即可。

分析：因为插入节点的颜色是红色，不会破坏任何规则。

解决方案：无。

分析：这时又可分为插入节点是父节点的左孩子还是右孩子，以及父节点是祖父节点的左孩子还是右孩子，由于对称性，我们只需要考虑其中一种即可。假设插入的节点是25，即如图4所示的位置。这时破坏了规则（4）红色节点的两个孩子节点都是黑的。

解决方案：将当前节点的父节点和叔叔节点改成黑色，祖父节点改为红色，把当前节点指向祖父节点。如图5所示。

情况4：当前节点的父节点是红色，叔叔节点是黑色，当前节点是其父节点的右孩子。

分析：这时破坏了规则（4）红色节点的两个孩子节点都是黑的。如图5所示。

解决方案：将当前节点的父节点作为新的当前节点，以新的当前节点为支点进行左旋。如图6所示。

[图片上传失败…(image-c45d5d-1594949705288)]

分析：这时破坏了规则（4）红色节点的两个孩子节点都是黑的。如图6所示。

解决方案：父节点改成黑色，祖父节点改成红色，将当前节点改为祖父节点，并以新的当前节点为支点进行右旋。如图7所示。

[图片上传失败…(image-492143-1594949705288)]

以上内容就是关于红黑树添加节点时的操作，本片博客参考了 ***/topics/350253651 。

红黑树的算法原理及讲解

性质1: 每个节点要么是 黑色 ,要么是 红色 。

性质2: 根节点是 黑色 。

性质3: 每个叶子节点(NIL)是黑色。

性质4: 每个 红色 节点的两个子节点一定都是 黑色 。

性质5: 任意一个节点到每个叶子节点的路径都包含 数量相同 的 黑节点 。俗称: 黑高 !

从性质5又可以推出:

性质5.1: 如果一个节点存在黑子节点,那么该结点肯定有两个子节点。

插入操作包括两部分工作:

注意: 插入结点,必须为 红色 ,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。如果插入结点是黑色,那么插入位置所在的子树黑色结点总是1,必须做自平衡。

最简单的一种情景,直接把插入结点作为根结点就行

注意: 根据红黑树性质2: 根结点是黑色。还需要把插入结点设为黑色。

处理: 更新当前结点的值,为插入结点的值

由于插入的结点是红色的,当插入结点的父结点为黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。

再次回想红黑树的性质2: 根结点是黑色。如果插入结点的父结点为 红结点 ,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这一点很重要,因为后序的旋转操作肯定需要祖父结点的参与。

依据红黑树 性质4可知,红色结点不能相连===>祖父结点肯定为黑结点

因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为: 红黑红

处理:

1.将P和U结点改为黑色

2.将PP改为红色

3.将PP设置为当前结点,进行后序处理

注意: 单纯从插入前来看,叔叔结点非红即空(NIL结点),否则的话破坏了红黑树性质5,此路径比其它路径多一个黑色结点。

处理:

处理:

该情景对应情景4.2,只是方向反转,直接看图

处理:

处理:

以上就是关于红黑树原理是什么建立过程,哪种树结构是一种自平衡二叉搜索树的方法的全部内容，以及红黑树的原理的相关内容,希望能够帮到您。