数据结构与算法笔记（四）

平衡二叉树

二叉查找树支持快速插入、删除、查找操作，各个操作时间跟树的高度成正比，理想情况下，时间复杂度为 O(logn)。但是，在极端的情况下，二叉树会退化成链表（比如按顺序插入一组数据），时间复杂度会退化到 O(n)。

为了解决这种问题，就有了平衡二叉树，红黑树就是平衡二叉树中的一种。

平衡二叉树的严格定义：二叉树中任意一个节点的左右子树的高度差不能大于 1。示意图如下：

最先被发明的平衡二叉查找树是 AVL 树，它严格符合上述定义，是一种高度平衡的二叉查找树。但是，很多平衡二叉查找树并未严格符合上述定义，比如经典的红黑树。

PS: 平衡二叉树发明的初衷是为了解决普通二叉查找树在极端情况下退化成链表，插入、删除等操作复杂度增加的问题。而“平衡”的意思就是让整棵树的左右子树比较均衡，从而使整棵树的高度相对低一些，插入、删除等操作效率更高。因此，尽管有些二叉树没有严格符合平衡二叉查找树的定义，但只要树的高度没有比 logn 大很多，仍然可以认为它是一棵平衡二叉树。

红黑树

红黑树（Red-Black Tree），简称 R-B Tree，它的每个节点都有颜色（红与黑）属性，是“出场率”很高的二叉树，它是一种不严格的平衡二叉树。示意图如下：

红黑树需要满足以下几个约束：

1. 节点是红色或黑色；

2. 根节点是黑色；

3. 所有叶子节点都是黑色（叶子是 NIL 节点）；

4. 每个红色节点必须有两个黑色的子节点（从每个叶子到根节点的所有路径上不能有两个连续的红色节点）；

5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

PS: 上面说的“叶节点”或“NIL节点”，不包含数据而只是充当树在此结束的指示，绘图中通常被省略。

平衡性调整

红黑树在插入或删除节点的过程中，上述第 3、4 点性质可能会被破坏，为了让它重新保持红黑树的性质，需要进行平衡性调整。

平衡性调整操作主要包括旋转（结构调整）和着色（红黑转换），其中旋转又分为左旋（rotate left）和右旋（rotate right）两个操作，左旋指的是围绕某个节点的左旋，右旋同理。左旋和右旋的操作示意图如下：

插入操作

红黑树规定，插入的节点必须是红色的。插入的情况分为多种，下面两种情况无须进行旋转操作：

1. 若插入节点的父节点是黑色的，则无需操作，仍满足红黑树的定义；

2. 若插入节点是根节点，那么直接将它变为黑色即可。

除此之外的其他情况都会违背红黑树的定义，需要进行平衡性调整（旋转和着色）。

case1

关注节点为 a，它的叔叔节点 d 为红色。则进行如下操作：

1. 将 a 的父节点 b、叔叔节点 d 的颜色都设置为黑色；

2. 将 a 的祖父节点 c 的颜色设置为红色；

3. 关注节点变成 a 的祖父节点 c；

4. 跳到 case2 或 case3。

操作示意图如下：

case2

关注节点是 a，它的叔叔节点 d 是黑色，a 是其父节点 b 的右子节点。则进行如下操作：

1. 关注节点变成 a 的父节点 b；

2. 围绕 b 左旋；

3. 跳到 case3。

操作示意图如下：

case3

若关注节点是 a，它的叔叔节点 d 是黑色，a 是其父节点 b 的左子节点。则进行如下操作：

1. 围绕 a 的祖父节点 c 右旋；

2. 将 a 的父节点 b、兄弟节点 c 的颜色互换。

操作示意图如下：

小结：插入后的修复操作是一个向 root 节点回溯的操作过程，一旦涉及的节点都符合了红黑树的定义，则修复操作结束。之所以会向上回溯是由于 case1 操作会将父节点、叔叔节点和祖父节点的颜色进行互换，可能会导致祖父节点不平衡，此时需要对祖父节点进行修复，以此类推。

删除操作

若删除的是叶子节点就直接删除；若不是叶子节点，会用对应的中序遍历的后继节点来顶替要删除的节点的位置。

删除操作的总体思想：从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否平衡，若不平衡则继续向上追溯调整。

删除节点的平衡性调整大概分为四种情况（对称情况下的操作类似）：

case1

待删除节点的兄弟节点是红色。则进行如下操作：

1. 围绕父节点 A 进行左旋；

2. 将父节点 A 和祖父节点 C 颜色互换；

3. 跳转到 case2、case3 或 case4。

操作示意图如下：

case2

待删除节点的兄弟节点是黑色，且兄弟节点的子节点都是黑色。则进行如下操作：

1. 将兄弟节点 C 的颜色设置为红色；

2. 关注节点上溯为父节点 A。

操作示意图如下：

case3

待调整节点的兄弟节点是黑色，且左子节点是红色、右子节点是黑色（兄弟节点在右边的情况。若兄弟节点在左边，就是右子节点是红色，左子节点是黑色）。则进行如下操作：

1. 围绕兄弟节点 C 右旋；

2. 将节点 C 和 D 变换颜色；

3. 跳到 case4。

操作示意图如下：

case4

待调整节点的兄弟节点是黑色，且右子节点是红色、左子节点是黑色（兄弟节点在右边的情况。若兄弟节点在左边，就是左子节点是红色、右子节点是黑色）。则进行如下操作：

1. 围绕父节点 A 进行左旋；

2. 删除 B 节点。

操作示意图如下：

删除修复操作是针对删除黑色节点才有的，需要从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑色节点可以借调的话，就只能向上追溯。

小结

红黑树是一种常见的平衡二叉树，结构稍微复杂了点，主要体现在插入和删除的时候需要进行旋转和变色的平衡性调整操作。

在 JDK 1.8 的源码中，TreeMap 和 HashMap 都用到了红黑树，以后打算根据相关代码做分析。

主要参考内容： 1. 极客专栏 2. https://zh.wikipedia.org/zh-hans/%E7%BA%A2%E9%BB%91%E6%A0%91 3. https://tech.meituan.com/2016/12/02/redblack-tree.html

相关阅读

数据结构与算法笔记（三）

Stay hungry, stay foolish.