平衡树

在应用中，我们经常需要维护一个“集合”结构，需要在集合上插入、删除元素，支持随机查找，基于元素的序结构实现顺序查找、询问排名、询问某一值域内元素个数、查询最大最小值、查询前驱后继等等操作。

如果用一个普通的线性表来维护“集合”，那么几乎所有操作的复杂度都达到了$O(n)$。一个改进是保证线性表的有序性，这样对序结构的操作就可以通过二分查找改进到$O(\log n)$，但插入和删除的复杂度依然是$O(n)$。我们想探究效率更高的数据结构来实现集合操作。

二叉查找树(Binary Search Tree, BST)

我们可以定义一棵二叉树，它的每个节点代表一个元素。我们要求对于每个节点，它的左子树上的元素值都小于该节点，右子树上的元素值都大于该节点。这样的树称为二叉查找树，我们的限制条件其实就保证了我们在查询某个元素的时候做二分，二分时元素访问的最大次数就是树的深度。

对于同样的集合元素，把它实现为二叉查找树的方式是多种多样的。完全二叉树的高度是$O(\log n)$，如果能够尽量保证树的形态是完全二叉树或接近于完全二叉树，那么上述集合操作的复杂度都能保证为$O(\log n)$。能保证尽量“平衡”的二叉查找树就是平衡树。

AVL树

平衡树的第一种实现方式是AVL树。我们对于每个节点维护一个以它为根节点的子树的高度，我们要求每个节点的两个儿子的高度之差不能超过1。通过简单地计算就会发现这样的限制条件能够把高度限制在$O(\log n)$以内。我们要讨论的关键问题在于，如何在树的结构被破坏后（通常只有插入和删除会破坏树的结构）维护这一性质依然成立。

AVL的插入

当我们要插入一个值的时候，我们首先到达这个位置应当处于的位置并把它插入。此时树上只有从这一节点直到根节点的路径上的节点的高度可能发生了变化（增加了1），这一变化可能导致对于某些节点左右子树的高度平衡被破坏，显然这些被破坏的节点也在这条链上。我们自下而上找到这条链上第一个被破坏的节点$A$， 由于它是因为某一子树$B$的高度增加1因此被破坏，因此之前这一子树的高度本来就恰好比另一子树$C$的高1。设$B$有外侧子节点$E$，内测子节点$D$。插入一定在$D$或$E$的子树上，因为插入节点作为叶节点是不可能直接破坏它父节点的平衡的。

如果插入发生在$E$上，设$C$的高度为$h$，那么$B$的高度必须是$h+2$，那么说明$E$的高度是$h+1$，由于$B$是平衡的（不然第一个被破坏的节点就是$B$了）并且高度因为插入了新节点而增加，因此$D$的高度在只能是$h$。此时如果对$B$做一次旋转，那么$A$是平衡的，高度为$h+1$，$E$的高度是$h+1$。因此$B$作为根节点高度依然为$h+2$，与先前$A$上未插入节点时的高度一致。这意味着我们不用继续向上做调整。我们只通过一次旋转就解决了问题。

如果插入发生在$D$上，设$C$的高度为$h$，那么$B$的高度必须是$h+2$，那么说明$D$的高度是$h+1$，由于$B$是平衡的且高度因为插入新节点而增加，$E$的高度是$h$。此时$D$的两个子节点高度一个为$h$，一个为$h$或$h-1$。如果对$D$连续做两次旋转，那么$A$是平衡的，高度为$h+1$，$B$也是平衡的，高度为$h+1$。因此$B$作为根节点高度依然为$h+2$，与先前$A$上未插入节点时的高度一致。所以我们也不用继续向上做调整。这次我们通过两次旋转解决了问题。

AVL的删除

在平衡树上删除一个节点时，如果这个节点有两个儿子，那么在它的子树中一定存在后继。那么我们可以转而删除后继节点，然后把要删除的节点赋值为后继节点。这样二叉查找树的性质依然是满足的。转化为后继节点有一个好处，因为后继是没有左子节点的，因此我们对删除的讨论只需考虑包括“没有子节点或只有一个子节点”的情况。

对于这样的节点，我们直接删除，如果有子节点就用子节点代替自己。这样做可能让以该节点为根的子树高度降低了1，此时它又有可能破坏了到根节点的链上的点的平衡性。此时我们往上爬升，检查每一个节点。有以下几种情况：

第一类，$A$原本左右子树高度是相等的。如果现在两个子树的高度没有发生任何改变，此时我们可以直接跳出；否则，某个子树的高度减了1，那么$A$的平衡性没被破坏，树高也不变，因此也可以跳出循环。

第二类，$A$原本的某一子树$B$比另一子树$C$高1。如果删除发生在$B$中，并且没有改变树高没有发生改变，那么跳出；如果树高减了1，那么$A$的平衡性依然保证，但整体树高减了1，因此需要继续检查父节点。如果删除发生在$C$中，如果树高不变，那么跳出；如果树高减了1，那么$A$的平衡被破坏了，并且$A$是自底向上第一个被破坏平衡的节点，这种情形与插入时的调整是本质上相同的，采取相同的调整策略即可，并依据新的根节点的高度是否被改变来决定是否要继续检查父节点。

红黑树(Red Black Tree, RBT)

红黑树是另一种可以实现“平衡”的二叉查找树。我们在它的每个节点上定义一个颜色——红色或黑色。颜色必须满足以下三个性质：

1. 根节点是黑色的。
2. 红色节点的儿子必须是黑色的。（等价于：不能出现两个连续的红色节点）
3. 对于任意一个节点$u$，在它的子树中，从它出发到所有空节点的路径上经过的黑色节点个数全部相等。其中空节点定义为“叶节点的子节点”以及“只有一个子节点的节点的另一个子节点”。

我们对颜色没有其它要求了。它把不平衡的范围限制在了两倍以内——它严格要求黑色节点的数量保持平衡，并通过限制“不能出现连续红色节点”使得深度之差不会超过两倍。考虑根节点，根据性质3从它出发到所有空节点经过的黑节点个数相等，设经过$M$个黑节点，那么最长的一条链也不能超过$2M$，因为红色节点必须间隔地出现，不然就会出现连续的红色节点了。因此树的高度不能超过$2M$，因此总的节点个数就不能超过$2^{2M}$。而一条链的长度还必须至少是$M$，因此总的节点个数至少得有$2^M$。这样我们就得到了由$M$确定的节点个数的一个取值范围，$2^M \leq |V| \leq 2^{2M}$，解得$\dfrac{1}{2}\log |V| \leq M \log |V|$。同时树的高度$M \leq h \leq 2M$。由此代入得$\dfrac{1}{2}\log |V| \leq h \leq 2\log|V|$。所以$h = O(\log |V|)$。

红黑树的插入

和AVL树一样，我们从根节点出发找到插入节点应该到达的位置，然后维护红黑树颜色的性质。

如果新节点被接在一个黑节点后面当儿子，那我们发现只需令新节点的颜色为红色，那么任何一条性质都不会被破坏，插入就直接完成了。

如果新节点被接在红节点后面了怎么办呢？此时如果把新节点染成红色，那么就出现了两个连续的红节点，矛盾；如果染成黑色，那么性质3就被破坏了，因为从根节点到其它空节点间经过的黑色节点数量不会发生任何变化，而新的空节点到根节点之间却多了一个黑节点。 可见光改变插入节点的颜色不能解决问题，此时必须对平衡树的结构本身进行调整，而这种调整就是平衡树的“旋转”操作和对树上其它节点的颜色的修改操作，我们需要对各种可能出现的情况做出不同的应对。下面来一一讨论：

设新插入的节点为X，父节点为P，祖父节点为G，祖父的另一个子节点为S。我们只需讨论P是红色的情况。由于P是红色，G必须是黑色。而S可能是红色也可能是黑色，所以我们首先基于S的颜色分类。

我们还必须考虑P，G，S这些节点的存在性问题。如果P不存在，那么X就是根节点，意味着这之前平衡树没有任何节点，所以直接令X为黑色（性质1）即可；既然P存在，如果G不存在，那么说明P是根节点，所以X被接在黑节点后面了，直接染红色即可；既然P，G都存在，如果S不存在，我们发现那时我们需要做的事和S存在且为黑色是一模一样的，所以这时候我们可以“认为S是黑色的”——事实上这是一个更具有一般性的想法，如果我们想象空节点都是黑色的，并且在数路径上的黑色节点时把空节点包括进去，那么红黑树的所有性质依然是满足的，因此“认为空节点是黑色”其实可以直接作为红黑树定义的一部分，只不过我们没有这么做。

如果S是黑色，此时有两种情况：(1) X，P，G三点共线。此时令P旋转，我们就找到了一种符合条件的着色方案：令X、G为红色，P、S为黑色。(2)X，P，G为折线，此时我们旋两次X，就找到了着色方案：令P、G为红色，X、S为黑色。可以验证从根节点到所有空节点经过的黑节点个数都与插入前保持一致。并且由于我们都把祖父位置的节点染成了黑色，性质2也满足。

如果S是红色，那么我们不旋转，而是直接令X、G为红色，P、S为黑色。可以验证从根节点到所有空节点经过的黑节点个数都与插入前保持一致。但原先祖父节点是黑色的，现在祖父节点变成红色了，如果它的父亲也是红色，那么性质2就被破坏了。此时需要不停向上修改节点颜色，问题变得非常复杂。一个最好的办法是通过某种方法避免出现“S是红色”这种情况。这种情况的出现是由于在插入位置到根节点的这条链上，出现了“一个黑色节点有两个红色儿子”这种情况，我们希望在这整条链上避免这种情况发生。当我们从根节点出发往下走的时候，一旦发现这种情况，即出现当前节点U为黑色而它的子节点都是红色，那么立即令U改为红色而子节点改为黑色。这样做可能使得U和fa(U)都是红色了，但所幸U的兄弟节点不可能也是红色，不然就和fa(U)的红色冲突了。因此这是和上一段讨论的“S是黑色”时发生的冲突一样的情况（当时我们相当于默认了X初始为红色），当时是没有子树的情况，我们发现有没有子树并不影响我们的讨论，所以我们采用当时的处理方式，如果三点共线就对父节点旋转一次，否则就把自己旋转两次，然后按照一样的方式重新着色，这样解决了冲突，可以继续往下走了。（如果U就是根节点，那么直接把U也染成黑色即可）。由于我们保证了往下走的过程中每个节点都不会同时拥有两个红色儿子，因此到了最后要插入的位置就不会出现红色兄弟的情况了！

红黑树的删除

平衡树中删除只需要讨论单个子节点的或没有子节点的节点。对于这样的节点，如果它是红色的，又很好办：如果它是红色的叶节点，那么直接删除即可；如果它是红色的并有一个子节点，那么直接把子节点接到父节点上然后删除它即可。所以我们只需考虑删除黑色点的情况。

对于黑色点，如果他有子节点并且子节点是红色的，由于他只有这一个子节点，我们只需保证删除后这个子树里的“黑高”不变，考虑把他和子节点的颜色交换，即子节点变成黑色，它自己变成红色，那么删除它以后子树的黑高确实不变，一切性质都保持得很好，所以我们也解决了。余下的问题就是如何删除“黑色叶节点”或“带有单个黑色子节点的黑色节点”了。

对于前者，如果我们直接删除该节点，会使得剩下的空节点黑高少1从而破坏性质3；对于后者，如果我们直接删除该节点会使得子树内的黑高都少1，也破坏性质3。这两个问题其实是同一个问题，只要我们能通过某一些调整使得以被删点为根节点构成的子树内的黑高都增加1，到那时我们直接删去该节点就正好能使子树的黑高不变。为此，我们来分情况讨论如何完成“使子树的黑高增加1”这项工作。

设要被删除的节点是N，它的父亲为P，兄弟为S，S有内侧儿子C，外侧儿子D（C，D要么都不存在，要么都存在，我们记得不存在的点可以当作黑色）。N一定是黑色，现在我们要分别讨论P、S、C、D的颜色。

假设S是红色，那么P，C，D只能是黑色。要让N的黑高增加1，我们旋S，并把P染红，S染黑。（这样保证了不出现连续红色节点）这样以后N，C，D的黑高都不变，一切性质依然满足。但我们成功地把N的兄弟节点变成了黑色，这样我们就只需解决兄弟节点使黑色的问题了！

所以现在我们在S一定是黑色的情况下讨论：

如果P是红色，C、D是红色——那么旋转S，再交换P、S的颜色即可；

如果P是红色，C、D是黑色——只要交换P、S的颜色即可；

如果P是黑色，C、D是红色——旋转S，把D染黑即可。

如果P是黑色，C、D是黑色——这时我们把S染红，那么C、D的黑高都减少了1，所以我们现在需要把N、C、D子树的黑高全都+1，这等价于给P子树的黑高+1。而这样我们就把问题转化了一个给深度更低的子树黑高+1了，我们往上递归，余下就不用管了。如果已经到了根节点无法递归了，说明整棵树上除了N的子树以外黑高都被减少了1，所以我们已经达成了“N的子树黑高增加1”的效果了。

这样我们就讨论完了所有C、D同色的情况。接下来考虑C、D不同色的情况：

我们假设C是内侧节点，D是外侧节点。如果C是黑色，D是红色，那么旋转S，再把D染黑即可。如果C是红色，D是黑色（我们将发现P的颜色不影响我们的操作正确性），那么旋转C并交换C、S的颜色，此时一切性质都保持，但红色节点到了外侧，黑色节点到了内测，这就转化为前一种情况了。

这样我们就解决了黑高增加1的问题。于是我们只需直接删除N点就完成了红黑树的删除操作。