数据结构拾遗——搜索树及其变种

你好，我是 N0tExpectErr0r，一名热爱技术的 Android 开发

我的个人博客：blog.N0tExpectErr0r.cn

前段时间对数据结构进行了复习，今天就写下这篇文章对二叉搜索树以及它的常见变种进行一下分析，主要涉及到了二叉搜索树、平衡二叉树以及红黑树。

二叉搜索树

具体代码实现：BSTMap.java

首先是我们最基本的搜索树：二叉搜索树。它的理论非常简单，只有一条基本的规则：对于树中的任意一颗子树，其左子树上所有节点的值一定小于其根节点的值，其右子树上所有节点的值一定小于其根节点的值。通过这样的理论，我们可以建立一颗如下的树：

它这样设计相比普通二叉树最大的优势就是其查找与插入效率。其查找、插入的复杂度为 O(log n)，带来了极大的查找效率提升，这也就是它为什么被称作『二叉搜索树』。它的搜索的原理与二分查找十分相似，每个子树上的根节点可以理解为这个子树中的『中间节点』，只需要将要搜索 / 插入的值与节点的值进行比较，并向对应方向进行进一步查找即可找到对应节点。

显然，对于二叉搜索树的实现，只需要在插入、删除时按照一定规则即可，它的节点与普通的二叉树没有什么不同：

class Node<T> {
    T data;
    Node<T> left;
    Node<T> right;
}

而对于插入，我们只需要在插入时通过与路径上的节点比较大小，就可以找到其应当插入的位置并进行插入。而对于删除，我们也只需与路径上的节点比较大小，从而找到需要删除的节点即可。类似下面的伪代码的原理：

if (值比当前节点小） {
    向左节点搜索
} else {
    向右节点搜索
}

仅仅靠这条规则，确实能够提高我们的查找效率了。但在某些极端情况下，二叉搜索树的表现却又不尽如人意。它最坏的情况是所有元素全部插入在了同一条链上，此时的二叉搜索树就像一条链表，其搜索、插入的复杂度又变回了 O(n)：

造成这一问题的原因很简单，那就是这条二叉搜索树的深度太深，从而影响了我们的查找、插入的效率。因此如果我们想要对二叉搜索树进行优化的话，最重要的一点应该就是减小深度。

显然，这条树上的元素完全可以以另一种形式来表达，从而降低深度以提高搜索效率。因此，我们可以设计一些算法，来对二叉搜索树进行重整。使得重整后的二叉搜索树在满足原有的规则的基础上，尽可能地减小它的深度。

平衡二叉树

具体代码实现：AVLMap.java

平衡二叉树就是为了解决这个深度问题而诞生的，它是一种特殊的二叉搜索树，相比于二叉搜索树增添一条规则：树上的任何一颗子树左右两个子树的高度差不超过 1。能满足这样的规则就能够叫做『平衡』。

为了维持这样的规则，平衡二叉树在每次插入节点后，都会进行一次对二叉树平衡性的调整，从而使得每次插入节点后二叉树都能够恢复平衡，其中主要用到了两个手段：左旋、右旋。

左旋如下图所示，以 E 为支点，将整颗子树进行了向左旋转，原根节点 E 的右节点 S 变为了新根节点，E 变为了 S 的左子节点，同时 S 的左子树变为了 E 的右子树。

右旋与左旋类似，是一种镜像操作。将整颗子树进行了向右旋转，原根节点 S 的左节点 E 变为了新根节点，S 变为了 E 的右子节点，同时 E 的右子树变为了 S 的左子树。

左旋和右旋都能够做到在保证二叉搜索树的基本性质的前提下，对子树的节点进行调整，从而辅助我们将树恢复平衡。

平衡二叉树需要通过左右两子树的深度来判断是否平衡从而确定是否需要进行调整，因此我们需要在其节点中加入左右子节点的深度信息。并且可以发现左旋右旋还需要对该树的父节点的指向进行修改，在非递归的实现中可能还需要用到父节点的信息。

class Node<T> {
    T data;
    int depth;
    Node<T> left;
    Node<T> right;
    [Node<T> parent;]
}

由于每次插入或删除后，都可能对整颗树的结构产生变化，因此平衡二叉树的调整策略是在每次插入或删除后，都会从插入的节点开始，递归地对每一个父节点进行平衡性调整，直到根节点为止。其插入、删除的步骤实际上与二叉搜索树是基本相同的，而平衡性调整主要分为以下四种情况：

其中 * 表示当前节点，可以看出来，情况 1 2、情况 3 4 分别互为镜像，因此对它们进行调整也是镜像调整。

情况 1、2

对于 1、2，可以看到当前节点、父节点、祖父节点是在同一条线上的。我们只需要分别以祖父节点 A 为支点进行一次右旋 / 左旋即可，此时仍然满足二叉搜索树的性质，并且达到了我们的目标：降低了深度：

情况 3、4

对于情况 3、4，可以看到当前节点、父节点、祖父节点并不是在同一条线上的。此时可以先以父节点 B 为支点，分别进行一次左旋 / 右旋，即可变为情况 1、2 的状态。之后再根据情况 1、2 的状态分别以祖父节点 A 为支点进行一次右旋 / 左旋：

在插入节点后，经过这样一次到根节点的递归平衡调整，该树就会回归平衡。通过这样的平衡调整，我们能够得到一颗平衡的二叉树，从而提高了搜索时的效率。不过，平衡二叉树的插入、删除操作相比二叉树搜索树的插入、删除，还多出了平衡性调整这一步骤，因此平衡二叉树的插入、删除的效率是不如二叉搜索树的。

红黑树

具体代码实现：RBMap.java

平衡二叉树看上去已经够完美了，那么红黑树相对与平衡二叉树又解决了怎样的问题呢？

平衡二叉树实际上是通过牺牲插入、删除的效率以提高搜索时的效率，因为它需要在插入后将树重新整理为一棵完全平衡的树。而对于红黑树我认为是一种对搜索效率与插入、删除效率的折中。

红黑树与平衡二叉树非常相似，不过它的平衡只是相对的平衡，并不是像平衡二叉树这样的完全平衡。它不再根据深度来判断一个树是否平衡，而是通过一些规则保证了二叉树的相对平衡，从而使得搜索效率提高，同时它的规则设计得十分巧妙，对于红黑树进行平衡调整不再需要像平衡二叉树那样不断地向上遍历进行调整，其插入最多只需要 2 次旋转，而删除最多只需要 3 次旋转，大大地提高了其插入、删除时的效率。

红黑树相对前面两种树来说复杂了很多，它将节点分为了红色节点与黑色节点，每个节点都有自己的颜色，并且定义了如下的规则：

每个节点不是红色就是黑色。
根节点总是黑色。
如果节点是红色的，则它的子节点必须是黑色的（反之不一定）。
从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。
插入的新节点都是红色的（NULL 节点必为黑色)。

而红黑树的平衡调整，都是以保证上面的规则为目的。也就是说，只要满足了上述规则，则该树一定是相对平衡的。

红黑树为了维持平衡，有三种调整的手段：变色、左旋、右旋。其中变色很好理解，就是改变节点的颜色，左旋右旋则与平衡二叉树一样。

由于红黑树调整平衡的手段不是递归，因此我们往往是以非递归的方式来实现，其节点除了携带颜色信息外，还需要携带父节点的信息：

class Node<T> {
    T data;
    boolean color;
    Node<T> left;
    Node<T> right;
    Node<T>	parent;
}

红黑树的调整策略是在每次插入、删除完成之后，对树进行平衡性调整，因此插入、删除的过程与二叉搜索树是基本一致的，而对于插入与删除的平衡性调整则各有不同。

插入

插入节点的不平衡主要是由于两个红色节点连续违反了规则 3 而造成的。

共有五种情况（N 为新插入节点）：

情况 1

第一次插入，则插入的是 root 节点，只需要将其颜色从红色变为黑色即可。

情况 2

插入的父节点若为黑色，则不需要任何操作，其仍然满足红黑树的规则。

情况 3

当前的节点父节点与叔叔节点（父节点的兄弟）均为红色，此时我们只需要将父节点及叔叔节点涂黑，祖父节点涂红，之后以祖父节点作为当前节点，继续进行调整操作。

情况 4

当前的节点父节点为红色，叔叔节点为黑色（空节点也是黑色），插入后祖父节点、父节点、新节点不在同一条线上，以父节点为支点进行左旋，这时就父节点就成为了当前节点的左子节点。祖父节点、父节点、新节点在同一条线上，变为了情况5：

情况 5

当前的节点父节点为红色，叔叔节点为黑色，插入后祖父节点、父节点、新节点在同一条线上。以祖父节点为支点进行右旋，同时互换父节点与祖父节点的颜色，此时父节点替代了祖父节点，并且祖父节点与新节点互为兄弟节点。从而继续达到平衡。

删除

删除比插入更为复杂，删除节点的不平衡主要是由删除黑色节点导致规则 4 不满足造成的。因此只有删除的节点为黑色节点时才需要进行调整。

共有六种情况（X 为删除节点）：

情况 1

删除的是根节点，只需用空节点替换根节点即可，不再解释。

情况 2

该节点的兄弟节点为红色，其余节点为黑色。可以对该节点的父节点进行左旋，之后互换父节点与兄弟节点的颜色。此时黑色节点数仍不满足条件，但该情况转变为了 4、5、6 的情况（兄弟节点为黑色的情况）。

情况 3

该节点的父节点、兄弟节点及兄弟节点的子节点都是黑色，此时可以将兄弟节点染成红色。从而使得黑色节点数一致了。不过这时通过父节点的路径比不通过父节点的路径少了一个颜色。此时可以从情况 1 开始对父节点重新进行平衡处理。

情况 4

该节点的父节点为红色，兄弟节点和兄弟节点的子节点是黑色。此时可以交换父节点和兄弟节点的颜色，这样的话不会影响其他路径，又维持了平衡。

情况 5

该节点为父节点的左节点，父节点颜色无所谓，兄弟节点为黑色，兄弟节点的左孩子为红色，右孩子为黑色。此时可以对兄弟节点进行右旋，并且互换它与它左孩子的颜色。之后变为了情况 6。

情况 6

该节点为父节点左节点，父节点无所谓，兄弟节点为黑色，兄弟节点的右节点为红色。此时可以对父节点进行左旋，并交换其与兄弟节点的颜色且将兄弟节点的右子节点颜色变为黑色（对父节点进行左旋并交换其与兄弟节点的颜色，可以使得经过当前节点的路径上的黑色节点数恢复原状。而对于原兄弟节点的右子节点，只需将其变为黑色即可恢复原经过兄弟节点的路径的黑色数目。）

红黑树的插入、删除效率相比于平衡二叉树的提高是十分明显的，插入最多旋转 2 次，删除最多旋转 3 次，同时其搜索效率相对与平衡二叉树虽然有所下降，但效率仍然是维持在一个非常高的水准。因此目前红黑树的应用十分广泛，例如 Linux 中虚拟内存的数据结构存储、Java 中的 TreeMap 及 HashMap、C++ 中的 map 均有红黑树的参与。

总结

下表是我个人对于二叉搜索树、平衡二叉树、红黑树三者的对比总结：

数据结构	插入、删除效率	搜索效率	实现难度
二叉搜索树	高	低	低
平衡二叉树	低	高	中
红黑树	中上	中上	高