【高阶数据结构】红黑树详解_stl 红黑树

前言

这篇文章我们再来学习一种平衡搜索二叉树——红黑树
红黑树和AVL树都是常见的自平衡二叉搜索树，它们都可以用于高效地支持插入、删除和查找等操作。虽然它们都能够保持树的平衡性，但在不同的应用场景下，红黑树和AVL树有各自的优势和适用性。

1. 红黑树的概念及性质

1.1 红黑树的概念

红黑树（Red-Black Tree）也是是一种自平衡的二叉搜索树，与AVL树不同的是它在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍（最长路径也不会超出最短路径的两倍，因此红黑树的平衡性要求相对宽松，没有AVL树那样严格），从而使搜索树达到一种相对平衡的状态。

1.2 红黑树的性质

红黑树具有以下特点

1. 每个结点不是黑色就是红色
2. 根结点必须是黑色的
3. 红色结点的两个子结点必须都是黑色的，这保证了没有两个连续的红色节点相连
4. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，也被称为NIL节点)
5. 任意结点到其每个叶子结点的简单路径上，黑色节点的数量相同：确保了树的黑平衡性，即红黑树中每条路径上黑色结点的数量一致。

大家可以对照着看一下上面的图，看它是否满足这些性质。

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中结点个数不会超过最短路径结点个数的两倍？（其实不带第4条就可以，加不加第4条都不会影响每条路径黑色结点数量是否相等）

那通过上面的性质我们可以得知，红黑树中的结点要么是黑色，要么是红色，这没什么可说的；然后要求根结点一定是黑色的，红色结点不能连续出现，如果出现了红色结点，那它的子结点必须是黑色的，然后还要求每条路径黑色结点的数量必须相等。
那这样其实就可以保证一棵红黑树中最长路径不超高最短路径的两倍。
当然实际中不同的红黑树情况是不一样的，所以我们这里来分析一种极端的情况：
大家想，如果一棵红黑树有红有黑，它里面如果有一条全黑的路径，那这条全黑的路径一定就是最短路径；
如果有一条是一黑一红，一黑一红…，这样黑红相间的，那他就是最长的路径。
然后它们里面的黑色结点个数又是相同的的，所以最长路径最多是最短路径的两倍，不可能超过最短路径两倍。
所以这样红黑树的高度就能够保持在一个相对平衡的范围内，当然他就没有AVL树那么严格。
比如这样的

那另外:

其实分析上面的性质，红黑树是可以全黑的，全部黑色结点，只要满足上面的性质即可。

然后大家思考一个问题，上面第四条性质——每个叶子结点都是黑色的(此处的叶子结点指的是空结点，也被称为NIL节点)，有什么用？

那大家先算一下这个红黑树有多少条路径？

如果不带空的话，我们可能会认为有5条，但是这里计算路径其实应该走到空（NIL），所以正确的应该是有11条路径。
所有我们可以认为这条规则就是为了更好的帮我们区分不同路径的。

然后再补充一个概念：

结点的黑高（黑色高度）：从某结点出发（不含该结点）到达任一空叶结点的路径上经过的黑结点总数

1.3 已经学了AVL树，为啥还要学红黑树

然后我们再来分析一个问题：

大家想，对于一棵红黑树来说，如果它里面全部的黑色结点一共有N个的话，那它的最短路径长度就差不多是$lo{g}_2(N)$。
然后整棵树的节点数量就是在【N，2N】之间。
所以最长路径长度就可以认为差不多是2$lo{g}_2(N)$
所以红黑树的查找最少是$lo{g}_2(N)$次，最多是2$lo{g}_2(N)$次，所以红黑树查找的时间复杂度是O($lo{g}_{2}N$)，计算时间复杂度前面的常数项可以省略嘛。
而AVL树也是O($lo{g}_{2}N$），但AVL树是比较严格的O($lo{g}_{2}N$），而红黑树是省略了常数项。
所以严格来说，红黑树的查找效率是比不上AVL树的（但对于计算机来说是没什么差别的），但是它们是同一个数量级的，都是O($lo{g}_{2}N$）。

那既然好像都差不多，为什么我们已经学了AVL树了，还要学红黑树呢？红黑树有什么优势吗？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/746928