【动态图文详解，史上最易懂的红黑树讲解】手写红黑树（Red Black Tree）

红黑树：一棵自平衡（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