红黑树：一棵自平衡（AVL）+二叉查找树(BST)
什么是红黑树
红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)。
红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树的性质（规则）
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。（保证这棵树尽量是平衡的。）
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。(不能有两个连续的红色节点)
2000的子节点不是黑色，不满足性质4，需要进行“自平衡”操作。
根节点是红色，根据性质1，需要进行“变色”操作。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
从性质5又可以推出：性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点。
Q&A
Q1.红黑树可不可以全为黑结点？
A：不可以。
反证法：假设有一颗红黑满二叉树结点都为黑色结点时，此时添加一个黑色结点，不满足（5）特性，但是就算经过旋转，也无法满足（5）特性，大家都是黑色，变不了红黑树。
红黑树的自平衡操作
前面讲到红黑树能自平衡，它靠的是什么？
三种操作：左旋、右旋和变色。
红黑树结点的叫法
红黑树结点的叫法如图所示。
我们把正在处理(遍历)的结点叫做当前结点，如图中的D，它的父亲叫做父结点，它的父亲的另外一个子结点叫做兄弟结点，父亲的父亲叫做祖父结点。
红黑树的自平衡的处理可以总结为：
自己能搞定的自消化；
自己不能搞定的叫兄弟帮忙；
兄弟都帮忙不了的，通过父母，找远方亲戚。
红黑树实现的源代码（Kotlin）
红黑树（RBT）的数据结构
public class RBNode<T>
{
bool color;//颜色
T element;//键值
public RBNode<T> left;//左节点
public RBNode<T> right;//右节点
public RBNode<T> parent;//父节点
}
插入
Before
Insert 6000
删除
查询
RB变色
3000 和 4000颜色互换。
不满足性质4：每个红色结点的两个子结点一定都是黑色。需要进行RB变色。
旋转
当破坏了平衡时，在调整的时候需要用到左旋和右旋：
4000节点不满足性质4：每个红色结点的两个子结点一定都是黑色。（5000和4000都是红色）
Single Rotate Left :
以4000节点为中心左旋。
RB 变色：
3000 ←→ 4000 RB color 交换
性能
(1) 查找代价：
由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)，可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。
(2) 插入代价：
RBT插入结点时，需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。
(3) 删除代价：
RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。
从根到叶子节点的最大路径不能大于最短路径的两倍长,大致上是平衡的，插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例。
如果查找、插入、删除频率差不多，那么选择红黑树。
参考资料
RBT 操作动画：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
https://www.jianshu.com/p/e136ec79235c
专注分享 Java、 Kotlin、Spring/Spring Boot、MySQL、redis、neo4j、NoSQL、Android、JavaScript、React、Node、函数式编程、编程思想、"高可用，高性能，高实时"大型分布式系统架构设计主题。
网友评论