红黑树原理和算法详细介绍,红黑树增加节点

本文目录

• 1.红黑树增加节点
• 2.红黑树和平衡二叉树时间复杂度
• 3.红黑树算法实现
• 4.平衡二叉树的查找效率呈什么数量级

红黑树增加节点

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

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

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

（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 。

红黑树和平衡二叉树时间复杂度

红黑树和平衡二叉树的区别：

红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

红黑树

红黑树是一种特定类型的二叉树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由RudolfBayer发明的，他称之为"对称二叉B树"，它现代的名字是在LeoJ.Guibas和RobertSedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的，它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。

平衡二叉树

平衡二叉搜索树（Self-balancingbinarysearchtree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。最小二叉平衡树的节点总数的公式如下F(n)=F(n-1)+F(n-2)+1这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

红黑树算法实现

这个周看算法导论，看到红黑树，看的我云里雾里绕啊。虽然最后看懂了，据我估计，要是过一个星期不看保证忘干净，因此决定写篇博客记录下红黑树。

红黑树是二叉树的一种，所以学习红黑树必须先搞懂二叉树。

如图，一颗二叉树是按照结点（二叉树结构）组成的。每个结点可以用链表结构标示。每个结点都应该有left right p ，他们分别指向左儿子，右儿子和父结点。每个结点还应该有个关键字key。如果某个儿子结点不存在，则相应位置就是nil。跟结点是树中唯一的父结点值是nil的节点。

设x为二叉树中的一个结点，如果y是x的左子树中的一个结点，则key[y]<=key[x]。如果y是x的右子树中的一个结点，则key[x]<=key[y]

我们有很多结点，如何将他组合成符合二叉树性质的二叉树呢？

我们一般通过下面两种方式遍历二叉树中的key

树根的关键字（key）在左子树和右子树的关键字之间输出就是 中序遍历算法

树根的关键字（key）在左子树和右子树的关键字之前输出就是 前序遍历算法

从图中我们能看出只要沿着各个结点的left指针查找下去，知道遇见nil 时候为止，就是最小值，最大值正好相反。

如图，3的前趋是2， 后继是6。

前趋后继的规律是什么呢?

前趋：如果结点x的左子树为非空，则x的前趋就是做子树中的最右结点。要是x的左子树为nil ，并且有前趋y（key是最最小值对应的x是没有前趋的），那么y是x的最低祖先，并且y的右儿子也是x的祖先。（x必须出现在y的右儿子的分支中，并且y是最低祖先）

后继：如果结点x的右子树为非空，则x的后继就是右子树中的最左结点。要是x的右子树为nil ，并且有后继y（key是最大值对应的x是没有后继的），那么y是x的最低祖先，并且y的左儿子也是x的祖先。（x必须出现在y的左儿子的分支中，并且y是最低祖先）

这里一定要搞明白，因为这里是红黑树删除的基础部分。

二叉树结点的删除分三种情况。

这里针对第三种情况的删除，我们不是删除z，而是删除的是z的后继y，把y的值赋值给z，这样不破坏树中的结构。变成了只是删除了一个叶子，这个叶子的特点是 左儿子是nil 。

红黑树是一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是RED或者Black。通过对任何一条从跟到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

树中每个结点包含五个域：color，key ，left，right 和p。如果某结点没有一个子结点或者父结点，则该结点相应的指针为nil。

从图中我们能看出每个叶子节点都是nil。nil对象都是一样的。干嘛不用一个nil 代替呢。因此如下结构。

旋转应该是二叉树的性质，只是普通二叉树没必要旋转。红黑树需要旋转来平衡树结构。

结果如下。

右旋的过程只是相反而已。

左旋的作用是将右儿子变成父结点。

右旋的作用是将左儿子变成父结点。

这样变化有什么用处呢？

我们知道，红黑树就是二叉树，因此向二叉树中插入数据没有啥区别。只是不过，当我们插入结点的某些时候就破坏了红黑树性质。因此，我们需要对二叉树进行调整让其适合红黑树的特性。

下面我们应该分析什么情况下插入结点能破坏红黑树。

假如我们插入的结点是黑色的，肯定是破坏了二叉树的性质5。（除非是根节点不破坏。）

但是我们插入的结点是红色的，不一定破坏二叉树的五条性质，为了方便，我们还是将二叉树插入的结点染成红色的比较好。(情况变少)

当我们插入一个红色结点可能破坏那些性质呢？第一条和第三条肯定是不会被破坏的，恒成立的。第五条因为插入的结点是红色的肯定也是成立的。这里可能不成立的是第二条（跟结点是黑的，要是插入的结点就是根结点）和第四条（如果一个结点是红的，它的两个儿子是黑的，因为要是插入的结点的父结点是红的话，那么父父结点就不符合要求了）。

因此，红黑树的结构被破坏就两种情况，不是性质2就是性质4.

性质2好解决，将结点染成黑色的就行了。不做分析。

我们重点分析性质4破坏，我们如何修正。

我们知道性质4被破坏的条件是父节点是红色的。

如图

这里我们分情况讨论 s 的颜色。

第一种情况 ： s的结点是红色。

这个情况，我们从根到左边的黑色结点数是2 ，右边的黑色结点数是2。

那么我们如何将其变成从跟到叶子的所有路线的结点数是2还不破坏红黑树呢？

只有下面一种变化才能符合红黑树，这样从根向下就符合红黑树了。

将祖父结点（跟结点）变成红色，p 和s 结点都变成 黑节点。

从上面的结果图我们能看出来， 根父 的颜色不定，可能是红色的，也可能是黑色的，那么我们就应该让 根 当做被插入的新节点，遍历根父 的兄弟的结点的颜色情况情况。这其实就是递归了。

要是每个根父的兄弟结点都是红色的话，那么遍历到根就结束了。将根染成黑色即可。要是根父的兄弟不是红色，那么就应该进入到第二种情况了。

第二种情况：s结点是黑色的。

这种情况不管如何变化，让总结点数不变的情况下，单纯染色根本没有办法让所有结点符合红黑树特性。让从根到叶子的路径含有相同的黑色结点。 那么怎么办呢？

我们知道，二叉树可以旋转，旋转可以改变树的结构。

这里我们用根做旋转（左旋或者右旋），结果如下

我们看看旋转结果，结果1，根变成p儿子的一边黑色结点树没有变化。而x的一边黑色结点数量减少了1。那我们如何让x一边增加1呢？只有如下一种情况，将p染成黑色，根染成红色。

结果2是无法达到我们的要求的，因此我们需要抛弃掉这种情况，让s是黑的时候只能变成结果1。

结果1所有的情况下都满足红黑树，不需要进行递归了。

这里我们需要看看什么情况下，x结点是p结点的儿子而不是根结点的儿子。这里我们需要看左旋右旋逻辑图了。

因此这里我们总结下结果1 的条件

结果2 就是剩下的。那么要是结果2的情况，我们应该如何处理呢。

那么结果2 在右旋的结构图就很清晰了。如下。p的右儿子是插入的结点x。

这种情况如何解决呢？

因为x是p的右儿子，所以旋转只能是左旋转。我们以p为根节点旋转。

结果如下

这样就变成了结果1 准备右旋转的的情况了。

同理，情况2的左旋图就变成了结果1准备左旋图的情况了。

总结

这里上面的方法是算法导论给出的，下面的是自己实现的。

删除操作和二叉树的操作一样，同样的只不过是删除的时候，可能引起对红黑树性质的破坏。

这里把删除二叉树的总结搬过来

这里我们罗列下这三种情况各个删除结点的结构。

二叉树第一种情况：没有儿子的情况。

二叉树第二种情况：只有一个儿子。左儿子或者右儿子。有四种情况

二叉树第三种情况：最多有一个右儿子

我们看出来，第三种情况不是第一种情况，就是第二种情况。因此这里我们只需要研究第一种情况和第二种情况就行了。

当x是红色的时候

将x删除，我们发现红黑树的黑色结点的数量不会发生任何变化。红黑树结构正常

我们发现不管什么条件下，删除红色结点红黑树不会发生任何变化。

这里我们需要讨论下 p 和 s的颜色，我们知道p 和s 分别只有红色和黑色，并且p 和s 不能同时为红色。那么p 和s的组合情况只有三种了。

我们发现不管哪一种情况都删除x的那一支都缺少一个黑色结点。

组合1

组合一通过染色是不可能达到树的平衡的。（有人好说了，把p染成黑色，s染成红色不就行了？我刚开始也犯了这个错误，要是s的两个儿子是红色怎么办呢？红色是不参与节点数计算的。）

因此我们这里直能通过旋转来改变树的结构来看看能不能达到我们的要求。我们以p旋转看看结果如下。

这貌似也不行，因为SL 可能是红色的，违反性质4。因此我们可以看出来，p是红色的情况下，旋转一次想让红黑树平衡依赖S的两个结点的颜色。

要是p左旋，那么s的左孩子是黑色的就可以。要是p右旋，那么s的右孩子是黑色的就可以了。

因此这里讨论下s的两个孩子的颜色情况。

如果SL 和SR 都是红色怎么处理呢？

单纯的旋转根本不可能让红黑树成立。只能先改变颜色在旋转了。

颜色改变如下

要是SL 和SR都是黑色的情况下

结构图如下

这种结构图 SL SR 都是nil。这种情况下旋转一下 p就行了。

SR SL只有一个颜色是红色的。如果p的删除分支是左儿子。那么SL 是红色，只能以s先右旋转。这样就变成了 SL SR都是黑色，但是s是红色的情况。是SL ,SR变化成平衡树的中间过程

最后这种情况，和SL SR 都是黑色一样的处理。

组合2

这里我们单纯靠染色是不可能实现树平衡的。因为删除x的结点的一支的结点都是黑色的。没有可以改变的红色结点存在。怎么办呢？我们只能通过旋转将删除的节点的一支上面增加红色结点才行。这里有个s是红色的，我们需要让其到删除结点分支上。

旋转结果

这样组合2删除结点的分支上有红色结点了。到这里我们发现这个地方的树可能违反红黑树了。

违反1：根是红色的话，s是红色违反性质4.

违反2：p结点黑节点数量还是对不上。违反性质5

不过没关系，要是我们能通过染色让树平衡的话，不用再调整树的结构的话，那么组合2也就算是解决了。

貌似通过染色也解决不了这个树平衡的问题，不过违反的红黑树的地方可以减少，我们将s染成黑色，p染成红色。

这里我们发现只有 p删除结点的一支，黑色结点数量少一。正好是组合一的情况。按照组合一的情况做一次旋转就可以解决问题

组合三

这种情况是最复杂的了。我们知道S要是红色，这就是组合2的情况，要是p是红色，那么就是组合1了。那我们想办法怎么让s或者p变成红色的呢？我们先从叶子节点找红色结点，看能不能让s或者p变成红色的。肯定是可以的。不过有一定条件。这里需要依赖SL,SR的颜色了。

当SL,SR都是红色，这种变化只通过改变颜色就可以让s变成红色，变成组合2的情况。

当SL,SR 只有一个红色的时候，通过改变颜色是不能达到要求的。因此我们就需要做旋转来达到要求。

当SL SR 都是黑色。没有红色，p结点一下是不能解决这个问题的。那怎么办呢？这样只能依赖p的父类了。不过这里需要注意的是p本身不平衡，我们这里依赖p的父类的时候，p需要是平衡的。如何平衡p呢？

我们只需要将s变成红色就可以了。p就平衡了。

不过这里注意，p的这一整支的所有分支都是少黑色结点1 的。

这里我们注意到p只有一个儿子。这里我们需要把p当成删除结点x的一个儿子。这样就转换成了x带一个儿子的情况了。这种情况如何平衡树。下面讨论一个孩子的时候包含，暂时不在这里讲解。

先拿一种情况分析 x是p的左儿子，x有一个左儿子

分析L 如果L是黑色的话，肯定是nil。因此可以将这种只有一个儿子的情况转换成没有儿子的情况。也可以这么说，要是x有儿子，儿子的颜色一定不是黑色。而是红色。如图

平衡二叉树的查找效率呈什么数量级

2019年7月26日

前言：树是一种数据结构的组织方式，不同的数据组织方式在数据的增删改查方面性能上有差异。例如ArrayList增删慢，其时间复杂度O(n），修改查询快，时间复杂度为O(1)；LinkedList正好与ArrayList相反；而红黑树在增删改查的时间复杂度均为O(log(n))。接下来，是我对树的简单总结和理解。

全文缺少配图，有时间补上

树：从直接前继和直接后继个数角度，可以这样定义， 0到1个直接前继，0到n个直接后继，其中n>=2。

节点 ：树就是由有限节点组成的一个具有层次关系的集合，数据就存在这些节点中。

根节点 ：最顶上的一个节点，没有父节点。

子节点 ：两个相连节点的关系。

叶子节点 ：某个节点下方没有任何分叉。

节点的高度 ：从某个节点出发，到叶子节点为止，最长简单路径上边的条数，称为该节点高度。

节点的深度 ：从根节点出发，到某节点边的条数，称为该节点的深度。

（1）树的左右高度查不能超过1；

（2）任何往下递归的左子树和右子树，必须符合第一条性质；

（3）没有任何节点的空树或只有根节点的树也是平衡二叉树。

（1）对于任意节点来说，它的左子树上所有节点的值都小于他，而他的右子树上所有节点都大于他。

遍历所有节点的常用方式有三种：前序遍历、中序遍历、后序遍历。

（1）在任何递归子树中，左节点一定在右节点之前遍历。

（2）前序、中序、后序，仅指根节点在遍历时的为止顺序。

前序遍历顺序：根节点、左节点、右节点；

中序遍历顺序：左节点、根节点、右节点；

后序遍历顺序：做节点、右节点、根节点；

二叉查找树由于数据不断增加或删除容易失衡，因此为了保持二叉树重要的平衡性，有很多算法实现，比如AVL树、红黑树等

AVL树是一种平衡二叉查找树，在增加或删除节点后通过树形旋转重新达到平衡。

右旋，以某个节点为中心，将它沉入当前右子节点的位置，而让当前的左子节点作为新树的根节点，也称为顺时针旋转。

左旋，以某个节点为中心，将它沉入当前左子节点的位置，而让当前右子节点作为新树的跟节点，也称为逆时针旋转。

与AVL树相比，红黑树并不追求所有递归子树的高度差不超过1，而是保证从根节点到叶子节点的最长路径不超过最短路径的2倍。

相比二叉查找树，有5个约束条件：

（1）节点只能是红色或黑色。

（2）根节点必须是黑色。

（3）所有NIL节点都是黑色的。NIL，即叶子节点下挂的两个虚节点。

（4）一条路径上不能出现相邻的两个红色节点。

（5）在任何递归子树内，根节点到叶子节点所有路径上包含相同数目的黑色节点。

总结即是“有红必有黑，红红不相连”，上述5个约束条件保证了：

（1）红黑树的新增、删除、查找的最坏时间复杂度均为O(logn);

（2）如果一个树的左子节点或者右子节点不存在，则均认定为黑色；

（3）红黑树的任何旋转在3次之内均可完成。（这个是怎么计算出来的？？？）

这里还需更加详细分析两者的区别

面对频繁的插入和删除，红黑树更为合适；

面对低频修改、大量查询，AVL树更合适。

以上就是关于红黑树原理和算法详细介绍,红黑树增加节点的全部内容，以及红黑树的原理的相关内容,希望能够帮到您。