随机二叉搜索树简介

这里我们介绍一种使用随机化技术的二叉搜索树结构，该结构能够保证所有操作的期望时间复杂度为 $O(\log n)$。

考虑下图所示的两棵二叉搜索树，每棵树都包含 $n = 15$ 个节点。

左边的树退化为一条链，高度为 $n − 1 = 14$；右边的树是完全平衡的，高度为 3。

想象一下这两棵树是如何构建的。左边的树是在一个空的 BinarySearchTree 上依次插入序列

后形成的。没有其他插入顺序能产生这棵树（你可以通过归纳法证明这一点）。而右边的树可以通过以下序列构建：

其他序列也可以生成这棵树，例如：

以及

事实上，有 21,964,800 种不同的插入序列可以生成右边的树，而只有 1 种序列能生成左边的树。

上述例子提供了一些经验性的证据：如果我们从 $0,...,14$ 中随机选取一个排列，并将其逐个插入到二叉搜索树中，那么我们更有可能得到一棵高度平衡的树（如图右侧），而不是一棵极度不平衡的树（如图左侧）。

我们可以借助随机二叉搜索树的概念来形式化这一现象。
随机二叉搜索树（random binary search tree）是指：取一个 $0,...,n−1$ 的随机排列 $x_0,...,x_{n−1}$，然后将这些元素依次插入一棵初始为空的 BinarySearchTree。所谓“随机排列”，是指 $0,...,n−1$ 的所有 $n!$ 种可能顺序出现的概率均等，即任一特定排列出现的概率为 $1/n!$。

注意，这里的值 $0,...,n−1$ 可以被任意一个大小为 $n$ 的有序集合所替代，而不会影响随机二叉搜索树的性质。元素 $x \in \{0,...,n−1\}$ 实际上代表的是在大小为 $n$ 的有序集合中排名为 $x$ 的元素。

在介绍随机二叉搜索树的主要结论之前，我们需要先简要讨论一类在分析随机结构时常出现的数值——调和数。
对于非负整数 $k$，第 $k$ 个调和数记作 $H_k$，定义为：

调和数 $H_k$ 没有简单的闭式表达，但它与自然对数 $\ln k$ 非常接近。具体地，

熟悉微积分的读者可能会注意到，这是因为积分 $\int_{1}^{k} \frac{1}{x} \, dx = \ln k$。考虑到积分可解释为曲线与 x 轴之间的面积，$H_k$ 的值可以被下界 $\int_{1}^{k} \frac{1}{x} \, dx$ 和上界 $1 + \int_{1}^{k} \frac{1}{x} \, dx$ 所夹住。下图提供了直观说明。

引理 1：在大小为 $n$ 的随机二叉搜索树中，以下结论成立：

1. 对于任意 $x \in \{0,...,n − 1\}$，查找 $x$ 的期望路径长度为 $H_{x+1} + H_{n−x} − O(1)$。

注：表达式 $x+1$ 与 $n−x$ 可分别理解为树中小于等于 $x$ 的元素个数和大于等于 $x$ 的元素个数。

1. 对于任意 $x \in (−1,n) \backslash \{0,...,n − 1\}$，查找 $x$ 的期望路径长度为 $H_{\lceil x \rceil} + H_{n-\lceil x \rceil}$。

我们将在下一节中证明引理 1。目前，先来看这两个部分告诉我们什么：第一部分表明，若在大小为 $n$ 的树中查找某个元素，则期望查找路径长度最多为 $2\ln n + O(1)$；第二部分则说明，即使查找的值不在树中，期望路径长度也大致相同。比较这两部分可知，查找已存在的元素与查找不存在的元素，在期望性能上差别不大。

引理 1 的证明

证明引理 1 的关键观察如下：在随机二叉搜索树 $T$ 中，对于开区间 $(−1,n)$ 内的值 $x$，其查找路径包含键为 $i < x$ 的节点，当且仅当在构造 $T$ 的随机排列中，$i$ 出现在集合 $\{i + 1, i + 2, ..., \lfloor x \rfloor\}$ 中任意元素之前。

为了理解这一点，请参考下图。

在集合 $\{i, i+1, ..., \lfloor x \rfloor\}$ 中的任意元素被加入之前，开区间 $(i−1, \lfloor x \rfloor + 1)$ 内所有值的查找路径都是相同的。（记住：两个值的查找路径不同，意味着存在某个树中节点与它们的比较结果不同。）设 $j$ 是集合 $\{i, i+1, ..., \lfloor x \rfloor\}$ 中在随机排列中最早出现的元素。显然，$j$ 会始终位于 $x$ 的查找路径上。如果 $j \ne i$，那么节点 $u_j$（包含 $j$）会在节点 $u_i$（包含 $i$）之前创建。之后当 $i$ 被插入时，它会被放入 $u_j.\text{left}$ 子树中，因为 $i < j$。然而，由于查找 $x$ 的路径在访问 $u_j$ 后会进入 $u_j.\text{right}$，因此永远不会访问这个子树。

类似地，对于 $i > x$，$i$ 出现在 $x$ 的查找路径上，当且仅当在构造 $T$ 的随机排列中，$i$ 出现在集合 $\{\lceil x \rceil, \lceil x \rceil + 1, ..., i−1\}$ 中任意元素之前。

注意到，若我们从 $\{0,...,n\}$ 的随机排列开始，则只包含 $\{i, i+1, ..., \lfloor x \rfloor\}$ 与 $\{\lceil x \rceil, \lceil x \rceil + 1, ..., i−1\}$ 的子序列本身也是各自元素的随机排列。因此，在每个子集中，任意元素出现在其他元素之前的概率相等。于是我们有：

基于这一观察，引理 1 的证明涉及调和数的简单计算：

引理 1 的证明：令 $I_i$ 为指示随机变量，当 $i$ 出现在 $x$ 的查找路径上时取值为 1，否则为 0。则查找路径长度为：

因此，若 $x \in \{0,...,n − 1\}$，查找路径的期望长度为：

对于 $x \in (−1,n) \backslash \{0,...,n − 1\}$，对应的计算几乎完全相同（参见图 4.b）。

总结

以下定理总结了随机二叉搜索树的性能表现：

定理：随机二叉搜索树可以在 $O(n\log n)$ 时间内构建完成。在随机二叉搜索树中，find(x) 操作的期望时间复杂度为 $O(\log n)$。

需要再次强调的是，定理中的“期望”是相对于构建树所用的随机排列而言的。特别地，它不依赖于 $x$ 的随机选择；该结论对每一个具体的 $x$ 均成立。