数据结构必知 --- 红黑树

1、什么是红黑树？

红黑树是一棵二叉搜索树，并且这棵树实现了弱平衡（严格的平衡是对于树中任意节点的左右子树高度差不超过1），确保没有一条路径会比其他路径长出两倍。弱平衡是指任意节点到到其子树中的叶节点所经过的黑色节点数相同，也可以称为黑色平衡（因为严格平衡的二叉搜索树AVL，维护成本太高，所以退而求其次）。

红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树最坏情况可以在O(log n)时间内完成查找，插入和删除操作。

2、为什么要引入红黑树？

• 普通的二叉搜索树可能退化为链表的情况，查询的效率将大大降低。

• 引入强平衡（树中任意节点的左右子树高度差不超过1），形如AVL树，树的维护成本太高。ps：windows对进程地址空间的管理用到了AVL树。

红黑树是牺牲了严格的高度平衡的优越条件为代价（统计性能更高），它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。

相对于要求严格的AVL树来说，它的旋转次数少，插入数据分布比较好用AVL树，数据分布复杂用红黑树。

3、红黑树的五大特性

• 节点是红色或者是黑色

• 根节点是黑色

• 每个叶节点（NIL或空节点）是黑色

• 每个红色节点的两个子节点都是黑色的（即不能有两个红节点相连）

• 任意节点到其子树中的叶节点（NIL节点）所经过的黑色节点数相同（最重要）

ps：注：红黑树引入了NIL节点，是一种虚拟节点，用于填充节点的左或右为空的位置，主要目的是便于判断从根节点到NIL节点，经过了多少黑节点。因此红黑树中的叶节点特指NIL节点，颜色必须是黑色。

4、红黑树的插入和删除

红黑树调整的两种方式：

• 旋转（左旋和右旋）：

  • 左旋：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。

  • 右旋：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。

• 变色（可能会产生连锁反应，多节点变色，目的是维持性质5）

添加操作（最多旋转两次）：

（1）将红黑树当作一颗二叉查找树，将节点插入。

（2）将插入的节点着色为"红色"。ps：如果插入是黑色节点，破坏第五条性质。

（3）通过一系列的旋转或着色等操作，使之重新成为一颗红黑树（满足红黑树的五个性质）。

删除操作（最多旋转三次）：

（1）将红黑树当作一颗二叉查找树，将节点删除。

（2）通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。

ps：插入和删除设计很多情况，可以参考维基百科学习。

5、应用

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

• 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.

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

• ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.

• java中TreeMap的实现.