算法 019：树：红黑树(R-B Tree)

红黑树的讲解在 JDK TreeMap & TreeSet 源码解读中有详细的展示，请参考集合源码 008：TreeSet & TreeMap 源码解析。这里再补充一些其它内容。

为什么要有红黑树

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

红黑树与 AVL 树的比较：

AVL 树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu 太快，可以忽略性能差异；
红黑树的插入删除比 AVL 树更便于控制操作；
红黑树整体性能略优于 AVL 树（红黑树旋转情况少于 AVL 树）。

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

具体性质如下：

每个节点颜色不是黑色，就是红色；
根节点是黑色的；
如果一个节点是红色，那么它的两个子节点就是黑色的（没有连续的红节点）；
对于每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点。

一个满足上述性质的红黑树示意如下（原文图片丢失，据性质构造的示意图，红色节点用描边标出）：

flowchart TD
    a13((13)):::black --> a8((8)):::red
    a13 --> a17((17)):::black
    a8 --> a1((1)):::black
    a8 --> a11((11)):::black
    a17 --> a15((15)):::red
    a17 --> a25((25)):::red
    a25 --> a22((22)):::black
    a25 --> a27((27)):::black
    classDef black fill:#263238,color:#fff
    classDef red fill:#ffcdd2,stroke:#c62828,color:#000

上图中从根到任何叶子的路径上黑色节点数相同，且不存在连续的红色节点，任意一条路径长度不超过最短路径的两倍。红黑树的查找、插入、删除都能保持在 O(logn)：

操作	复杂度
查找	O(logn)
插入（含修复）	O(logn)
删除（含修复）	O(logn)
旋转次数	插入至多 2 次、删除至多 3 次（少于 AVL 树）

插入与删除后如何通过变色和左右旋修复红黑性质，配合 JDK 源码的逐情况剖析见 TreeMap 源码解析。

应用场景

Java ConcurrentHashMap & TreeMap
C++ STL: map & set
linux 进程调度 Completely Fair Scheduler，用红黑树管理进程控制块
epoll 在内核中的实现，用红黑树管理事件块
nginx 中，用红黑树管理 timer 等

其它参考

@skywang12345 写的红黑树实现 https://www.cnblogs.com/skywang12345/p/3245399.html
30 张图带你彻底理解红黑树 https://www.cnblogs.com/kumufengchun/p/11169138.html
浅析红黑树（RBTree）原理及实现 https://blog.csdn.net/tanrui519521/article/details/80980135

系列导航

上一篇：树：平衡二叉树（AVL）
下一篇：树：哈夫曼树（Huffman Tree）
相关篇：TreeSet & TreeMap 源码解析（红黑树在 JDK 中的完整实现）、二叉搜索树 BST（BST → AVL → 红黑树的演进起点）

CHARLIE SAYS