红黑树详解：从二叉查找树到自平衡二叉树

红黑树详解：从二叉查找树到自平衡二叉树

引用

CSDN

1.

https://blog.csdn.net/qq_28584889/article/details/88702166

红黑树是一种自平衡二叉查找树，在计算机科学中被广泛应用于实现关联数组，如Java中的TreeMap和C++中的map。本文将从二叉查找树和平衡二叉树的基本概念出发，逐步深入讲解红黑树的定义、性质以及插入操作的具体步骤。

二叉查找树

二叉查找树，又名二叉排序树、二叉搜索树，具有以下特性：

• 左子树上所有的节点的值都小于或等于他的根节点上的值
• 右子树上所有节点的值均大于或等于他的根节点的值
• 左、右子树也跟分别为平衡查找树

举个二叉树的例子：

可以看到如果要查询10的话，10>9

因此到他的右子树，右子树根节点为13，10<13

因此到其左子树，左子树根节点为11>10

到其左子树，为10，找到相应的节点

不过二叉查找树有一些问题，可能会出现不平横的情况，即如下图所示的情况

从这种情况可以看出，明显存在左子树和右子树深度相差过多，在使用平衡情况下的二叉查找树是时间复杂度为logn，而出现这种极端情况的话，想要查9的位置就需要每一次都遍历下一个右子树，很有可能时间复杂度变为n(与数组普通查询的时间复杂度相同)。

基于上述情况，引入了平衡二叉树，红黑树即为类似于平衡二叉树的一种。

平衡二叉树(AVLTree)

平衡二叉树最大的作用就是查找,AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。AVL树的效率就是高在这个地方。如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理, 那么创建一颗平衡二叉树的成本其实不小。这个时候就有人开始思考，并且提出了红黑树的理论，那么红黑树到底比AVL树好在哪里？

红黑树与AVL树的比较：

1. AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异
2. 红黑树的插入删除比AVL树更便于控制操作
3. 红黑树整体性能略优于AVL树（红黑树旋转情况少于AVL树）
4. 平衡二叉树的性质要求左右子树深度的差值的绝对值不超过1；而红黑树的性质是保证最长路径不超过最短路径的二倍。

红黑树的性质

红黑树是一棵二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。

具体性质如下：

1. 每个节点颜色不是黑色，就是红色
2. 根节点是黑色的
3. 如果一个节点是红色，那么它的两个子节点就是黑色的（没有连续的红节点）
4. 每个叶节点都是黑色的空节点(NIL节点)
5. 对于每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点

红黑树的插入

红黑树插入节点过程大致分析：

RBTree为二叉搜索树，我们按照二叉搜索树的方法对其进行节点插入
RBTree有颜色约束性质，因此我们在插入新节点之后要进行颜色调整
具体步骤如下：

1. 根节点为NULL，直接插入新节点并将其颜色置为黑色
2. 根节点不为NULL，找到要插入新节点的位置
3. 插入新节点
4. 判断新插入节点对全树颜色的影响，更新调整颜色，如果调整颜色仍不能达到红黑树的平衡，则进行相应的旋转操作；

首先红黑树的插入其实不是那么容易实现的，以前搜索树的插入我们很容易理解现在我们首先思考一个问题，你插入节点的默认颜色是RED或BLACK？
这里我们需要根据性质来思考，首先如果插入黑节点，这个可以直接插入无论它的父亲是什么颜色，但是红黑树的性质是每条路径的黑色节点数目相同这个时候你再想想那其他路径的黑色节点数目一定比你现在少一个节点，所以调整起来是非常繁琐的. 插入红节点不需要调整其他路径，如果它的父亲为黑，那么直接插入，如果他的父亲为红那么在该路径上面开始分情况调整. 所以插入节点默认颜色一定要为红.如果为黑调节成本太大了. 接下来开始插入节点如果插入节点的父亲为黑那么直接插入后返回不需要做任何调整. 但是如果插入节点的父亲为红，那么就需要调整了.

一个红黑树的例子

向红黑树中插入节点14(一般默认插入节点是红色的，具体原因上面讲过的)

因为插入节点14的父节点15是黑色节点，所以插入之后就已经是平衡的了，不需要调整。

在原树上插入20；

可以看到，插入以后树已经不是一个平衡的二叉树，而且并不满足红黑树的要求，因为20和21均为红色，这种情况下就需要对红黑树进行变色，21需要变为黑色，22就会变成红色，如果22变成红色，则需要17和25都变成黑色

而17变成黑色显然是不成立的，因为如果17变为黑色，那么13就会变为红色，不满足二叉树的规则，因此此处需要进行另一个操作---------左旋操作

左旋：下图就是一个左旋的例子，一般情况下，如果左子树深度过深，那么便需要进行左旋操作以保证左右子树深度差变小

对于上图由于右子树中17变为黑色以后需要把13变成红色，因此进行一次左旋，将17放在根节点，这样既可保证13为红色，左旋后结果

而后根据红黑树的要求进行颜色的修改

进行左旋后，发现从根节点17，到1左子树的叶子节点经过了两个黑节点，而到6的左叶子节点或者右叶子节点要经历3个黑节点，很显然也不满足红黑树，因此还需要进行下一步操作，需要进行右旋操作

右旋：与左旋正好相反

由于是从13节点出现的不平衡，因此对13节点进行右旋，得到结果

而后再对其节点进行变色，得到结果

这便是红黑树的一个变换，它主要用途有很多，例如java中的TreeMap以及C++中的map、set、multimap、multiset底层实现都是红黑树。