红黑树

第 12 章介绍了一棵高度为 $h$ 的二叉搜索树, 它可以支持任何一种基本动态集合操作, 如 SEARCH、PREDECESSOR、SUCCESSOR、MINIMUM、MAXIMUM、INSERT 和 DELETE 等, 其时间复杂度均为 $O(h)$ 。因此, 如果搜索树的高度较低时, 这些集合操作会执行得较快。然而, 如果树的高度较高时, 这些集合操作可能并不比在链表上执行得快。红黑树 (red-black tree) 是许多平衡搜索树中的一种, 可以保证在最坏情况下基本动态集合操作的时间复杂度为 $O(\log n)$

定义

为了保持 AVL 树的平衡性， 插入和删除操作后， 我们需要非常频繁地调整全树整体拓扑结构，代价较大， 为此在 AVL 树的平衡标准上进一步放宽条件， 引入了红黑树的结构。

一棵红黑树是满足下面红黑性质的二叉搜索树

1. 每个节点非红即黑
2. 根节点是黑色的
3. 每个叶节点 ( NIL ) 是黑色的
4. 如果一个结点是红色的， 则它的两个子结点都是黑色的
5. 对每个结点， 从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

• 结论1: 从根到叶节点的最长路径不大于最短路径的 2 倍

• 结论2: 有 $n$ 个内部结点的红黑树的高度 $h \leqslant 2 \log_2 (n+1)$

从某结点出发(不含该结点) 到达一个叶结点的任一简单路径上的黑结点总数称为该结点的黑高 (记为 bh ), 黑高的概念是有上面的性质 5 决定的。 根节点的黑高称为红黑树的黑高。

应用

1. 广泛用于 C++ 的 STL 中，map和set都是用红黑树实现的

2. Linux的完全公平调度(CFS)利用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间

3. IO多路复用的 epoll 的实现采用红黑树组织管理的 sockfd ，以支持快速的增删改查

4. Nginx用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器

5. Java中的 TreeMap 的实现