Python Balanced Search Tree 平衡查找树

Question

介绍

使用二叉搜索树对某个元素进行查找，虽然平均情况下的时间复杂度是 O(log n)，但是最坏情况下（当所有元素都在树的一侧时）的时间复杂度是 O(n)。因此有了平衡查找树（Balanced Search Tree），平均和最坏情况下的时间复杂度都是 O(log n)

平衡因子（Balance Factor, BF）的概念：左子树高度与右子树高度之差

平衡查找树有很多不同的实现方式：

• AVL 树
• 2-3查找树
• 伸展树
• 红黑树
• B树（也写成B-树，B-tree，中间的“-”代表杠）
• B+ 树

AVL 树

也叫平衡二叉树（Balanced Binary Tree），AVL是提出这种数据结构的数学家。概念是对于所有结点，BF 的绝对值小于等于1，即左、右子树的高度之差的绝对值小于等于1

在各种平衡查找树当中，AVL 树和 2-3 树已经成为了过去，而红黑树（red-black trees）看似变得越来越受人青睐 —— Skiena

AVL 树在实际中并没有太多的用途，可支持 O(log n) 的查找、插入、删除，它比红黑树严格意义上更为平衡，从而导致插入和删除更慢，但遍历却更快。适合用于只需要构建一次，就可以在不重新构造的情况下读取的情况。

2-3查找树

理解2-3查找树是为了更好地理解红黑树做准备。2-3查找树是一颗BST，它的结点既可以是一个2-结点，即含有两个子结点的结点（和普通二叉树一样），也可以是一个3-结点，即自身有两个value，并且含有三个子结点。3-结点的左链接指向的树中的值都小于该结点的值，中链接指向的树中的值介于该结点的两个值之间，右链接指向的树的值都大于该结点的值。一棵完美平衡的2-3树中的所有空结点到根结点的距离是相同的。

为了保持平衡性，对2-3查找树的插入操作需要分为很多种情况进行调整，这里不打算介绍，因为稍后会重点介绍红黑树的插入操作。但是，就算理解了2-3树插入操作的原理，我们离真正的实现还有一段距离，其中一个原因就是我们需要维护两种不同类型的结点，需要大量的代码。

红黑树

红黑树（Red-Black Tree）是一种平衡查找树的实现方式，就像AVL树也是平衡查找树的一种实现方式一样，但是AVL树对于平衡的要求更加严格，导致插入/删除的时候更慢。红黑树的定义使得它能保持一定的平衡性（不像AVL那么严格的平衡），同时又能有一定的灵活性（flexibility）。

红黑树首先是一个二叉搜索树，同时必须要满足以下四个性质：

• Every node is colored red or black. 每个结点要么是红色，要么是黑色
• All leaf (nil) nodes are colored black. 所有的叶结点都是黑色
• Every red node has black children. 红色结点的子结点必须是黑色
• From any node, the number of black nodes on any paths to leaves is the same. 对任何一个结点来说，从这个结点到叶结点的任何路径，所经过的黑色结点的数量应该是相同的

（第二条注意一下，定义中所说的叶结点指的是所有为 None 的结点。当我们画一棵正常的二叉树的时候，通常都不会将这些None结点画出来）

当使用上面的定义来判断一棵树是不是红黑树时，只能逐条定义进行判断，并不存在通过这四个规则推导出来的一个通用简明的判定红黑树的规则。可以看到红黑树并没有像AVL那样规定左右子树的高度之差必须小于1，但是，通过红/黑结点的定义以及约束，红黑树也能像AVL那样维持自己的平衡性。红黑树的最大高度是 2log(n)

如果把一个红黑树中的所有结点都涂成黑色，这棵树仍然是一棵红黑树，但是退化成了一棵完美平衡的二叉树，所以可以看到红黑树的性质使得它有了更多的灵活性。

在红黑树中搜索元素和BST是一样的。但是，当进行插入/删除操作的时候，红黑树的性质会被改变，这时，需要通过变色以及旋转的方式来使其恢复红黑树的性质。进行插入/删除操作的时候，第一步还是按照BST的规则将一个结点插入/删除，然后第二步是恢复红黑树的性质。整个操作的时间复杂度是 O(log n)

先介绍一下如何进行旋转，分为两种情况：左旋（left rotation）和右旋（right rotation）。旋转操作之后，二叉搜索树BST的性质仍然不变。旋转的时间复杂度是常数时间。

那么在插入/删除结点之后，如何通过变色和旋转的方法恢复红黑树的性质呢？以插入为例，首先按照BST中插入结点的方式将结点插入到红黑树中，将其着色为红色（之所以着色为红色是为了避免对规则四的破坏，修复规则四要复杂得多，而着色为红色只破坏了规则三）。然后从新插入的结点开始，逐层向上修复那些破坏了红黑树性质的结点。可以分为以下三种情况进行修复：

CASE 1：要修复的红色结点的 cousin 也是红色结点（cousin 就是其父结点的兄弟结点）

这种情况比较容易解决，只需要变色（re-color）就可以。变色之后，图中不再有与规则3冲突的部分，同时每条路径上黑色结点的数量也没有变化。唯一可能出现问题的就是当把图中最上面那个结点变为红色结点之后，它的父结点可能也是红色结点。但是，即便出现这种情况，我们也完成了将问题结点向上转移的工作，接下来只需要继续往上修复问题结点就行了。

CASE 2：要修复的红色结点的 cousin 是黑色结点，并且这两个结点同向（都是左结点/都是右结点）

对于这种情况，需要首先经过一次旋转操作将其转换为 CASE 3 中的情况，然后再按照 CASE 3 进行处理。旋转一次之后，要修复的结点就变为了和它的 cousin 不同向，即 CASE 3

CASE 3：要修复的红色结点的 cousin 是黑色结点，并且这两个结点不同向

这种情况，经过一次旋转操作和一次变色操作就能彻底修复，满则红黑树的性质，不会将问题结点向上层转移。首先，将问题结点的父结点进行右旋，然后进行变色操作，使红色结点的子结点都是黑色，并且不改变每条路径上黑色结点的数量。操作完成之后，图中最上面的结点是黑色，因此肯定不会与上层的结点发生冲突，黑色结点可以是任何结点的子结点。

可以看到，要修复的永远都是红色结点，并且都是修复规则 3 —— 红色结点的子结点也是红色结点。在三种修复的情况中，只要开始进行旋转操作（CASE 2 和 CASE 3），那么修复就会在至多两次旋转操作之内结束。而 CASE 1 的变色操作每次会将有问题的结点向上转移两层，所以至多在 O(log n) 时间内就会结束。所以插入/删除操作的时间复杂度：BST的插入/删除时间复杂度 O(log n) + 恢复红黑树性质的调整操作 O(log n)，故时间复杂度为 O(log n)

关于红黑树的理解，强烈推荐下面的视频，跟着视频慢慢过一遍能够让自己有一个比较清楚的理解：

• Algorithms/Red-Black-Tree-1 - Shai Simonson（视频）
• Algorithms/Red-Black-Tree-2 - Shai Simonson（视频）