下面的题目是《算法导论（第三版）》中红黑树一章的思考题13-4，主要介绍与分析了Treap树的一些知识和性质。本文也将以原题内容作为线索，通过证明和解答其中的问题，来说明Treap树的主要特点。

有些问题也是比较棘手的，受限于个人能力，因此并无法保证所有证明过程的正确性，而在合适的时机，我将会给出社区讨论链接。

原书中对部分地方配有图片描述，在这里，目前没有添加配图，如果有时间再行补上。

定义

如果将一个含 n 个元素的集合插入到一棵二叉搜索树中，所得到的树可能会相当不平衡，从而导致查找时间很长。然而从12.4节（随机构建二叉搜索树）可知，随机构造二叉搜索树是趋向于平衡的。因此，一般来说，要为一组固定的元素建立一棵平衡树，可以采用的一种策略就是先随机排列这些元素，然后按照排列的顺序将它们插入到树中。

如果没法同时得到所有的元素，应该怎样处理呢？如果一次收到一个元素，是否仍然能用它们来随机建立一棵二叉搜索树？

我们将通过考察一个数据结构来正面回答这个问题。一棵treap树是一棵更改了结点排序方式的二叉搜索树。图13-9显示了一个例子。通常，树内的每个结点 x 都有一个关键字 x.key。另外，还要为每个结点指定 x.priority，它是一个独立选取的随机数。假设所有的优先级都是不同的，而且所有的关键字也是不同的。 treap树的结点被排列成让关键字遵循二叉搜索树的性质，且优先级遵循最小堆顺序性质：

• 如果 v 是 u 的左孩子，则 v.key < u.key。
• 如果 v 是 u 的右孩子，则 v.key > u.key。
• 如果 v 是 u 的孩子，则 v.priority > u.priority。

这两个性质的结合就是这种树被称为“treap”树的原因：它同时具有二叉搜索树和堆的特征。

基础性质

用以下方式考虑treap树是会有帮助的。假设将已有相应关键字的结点 `x_1, x_2, …, x_n`插入到一棵treap树内。得到的treap树是通过将这些结点以它们的优先级（随机选取的）顺序插入一棵正常的二叉搜索树形成的，即 `x_i.prio rity < x_j.prio rity`表示 `x_i`在`x_j`之前被插入。

a. 证明：给定一个已有相应关键字和优先级（互异）的结点`x_1, x_2, …, x_n`组成的集合，存在唯一的一棵treap树与这些结点相关联。

这第一个问题很容易给出一个非形式化的描述来证明。我们根据treap树的定义可以知道，当给定了一个结点集合之后，那么二叉树的根节点肯定是这些结点之中优先级最小的那个结点（堆的性质），然后又可以按照二叉搜索树的要求，将剩余的元素分为两个部分，分别用于构建根节点的左右子树。概括来讲，给定一个结点的集合之后，我们可以通过下列步骤来构建起一个treap树：

1. 从元素集合里面选取优先级最小的那个元素（集合为空，则选择nil）；
2. 将剩余元素按照二叉搜索树要求方式分为两个部分，其中一部分所有元素均小于上面选择的元素，而另一部分则不小于；
3. 以上面获得的两部分元素作为集合，转到步骤1递归执行，并将子过程选择的元素分别作为当前选取元素的左右孩子。

由于每次运行步骤1的时候，选择的元素是唯一的，因此从第一次执行开始，对于一个给定的集合，我们每次执行的结果都是一定的，所以最后得到的treap树也是唯一的。

b. 证明：treap树的期望高度是`Theta(lgn)`，因此在treap树内查找一个值所花的时间为`Theta(lgn)`。

对于这一问题，我的答案最多只能作为参考思路，我并不确定解答过程的正确性。

对于一个有 n 个元素的treap树，我们假设所有元素的关键字分别为 `k_1, k_2, …, k_n`，所有的优先级集合为 `p_1, p_2,…,p_n`，然后定义`A_(ij)`表示一个关键字为`k_j`、优先级为`p_i`的一个结点。因此一个 n 元素的treap树的高度 `h_n` 就是以结点 `A_(1j)` 为根的树的高度，并且我们可以知道根节点的两个子树分别有 `j-1` 和 `n-j` 个元素，其高度也可以表示为 `h_(j-1)` 和 `h_(n-j)`。因此，我们可以得到下面的表达式：

`h_n = MAX(h_(j-1), h_(n-j)) + 1, 1 <= j <= n`

因此要计算`h_n`的期望，我们可以通过对 j 的所有取值所得结果取平均值，即：

`E(h_n) = 1/n sum_(j=1)^n MAX(h_(j-1), h_(n-j)) + 1`

其中我们可以令`h_0 = 0`。

使用代入法来证明。即我们需要证明：存在一个正数C，使得`h_n <= Clgn`。在这里，我们假设对于上面的MAX方法，每次返回的均是第二个参数的值，那么我们可以得到：

`E(h_n) = 1/n sum_(j=0)^(n-1) h_j`

`E(h_n) = 1/n sum_(j=1)^(n-1) Clgj`

`E(h_n) = C/n lg(prod_(j=1)^(n-1))`

`E(h_n) <= C/n lg(n!)`

`E(h_n) = C/n Theta(nlgn)` 因为`lg(n!) = Theta(nlgn)`

所以可推出`E(h_n) <= C/n * nlgn = Clgn`，同理也可推出期望值下限为`Omega(lgn)`。因此treap树的期望高度为`Theta(lgn)`。

插入操作

让我们如何将一个新的结点插入到一个已存在的treap树中。要做的第一件事就是讲一个随机的优先级赋予这个新结点。然后调用成为TREAT_INSERT的插入算法，其操作如图13-10所示。

暂时没有配图，因此简述一下插入过程，当给定一个要插入的结点时，我们假设这个结点的关键字和优先级都已经设置好了，并且其左右孩子的值均为nil。

首先我们按照二叉搜索树的插入过程，将结点插入到相应的位置，这个过程只考虑结点的关键字；然后接下来我们就要开始通过旋转操作来恢复treap树的堆性质了，这个过程只考虑结点的优先级即可。

c. 解释TREAP_INSERT是如何工作的。说明其思想并给出伪代码。（提示：执行通常的二叉搜索树插入过程，然后做旋转来恢复最小堆顺序的性质。）

关于插入过程的工作概要已经在题目的提示以及上面的简述中说明了。之所以这么做可行，是因为treap树的关键字和优先级属性之间是独立的，相互之间并不存在影响，因此我们可以单独分别处理每一个属性。

1. 首先进行常规二叉搜索树的插入过程，也就是一次二叉树简单路径的搜索过程，最后将结点插入到某一个叶结点；

   这个时候，整个树的关键字集合已经满足二叉搜索树的性质了，但是优先级顺序不一定满足，因此我们需要通过旋转来恢复最小堆顺序的性质，因为旋转操作不改变二叉搜索树的性质；

2. 接下来从被插入的结点开始，如果其优先级小于父结点的优先级，则说明最小堆顺序的性质被破坏，根据结点是父结点的左孩子还是右孩子，执行相应的右旋或者左旋操作，然后重复这一过程直到恢复最小堆顺序的性质。

伪代码：

TREAP_INSERT(T, z)
    TREE_INSERT(T, z)   // 二叉搜索树的插入过程
    while z.priority < z.p.priority
        if z == z.p.left
            RIGHT_ROTATION(T, z.p)  // 右旋
        else
            LEFT_ROTATION(T, z.p)   // 左旋

这里我们不用考虑如果 z 为根节点的时候的边界情况，因为我们假设在树中引入了哨兵T.nil来代替nil值，因此根节点的父结点也就是T.nil，我们将其优先级设置为`-oo`，这样就可以使我们减少对边界条件的判断（这也是旋转过程的基本假设条件）。

d. 证明：TREAP_INSERT的期望运行时间是`Theta(lgn)`。

证明：首先，对于TREE_INSERT过程的调用期望运行时间为`Theta(lgn)`。

然后我们可以分析第3到7行的while过程运行时间。第一次循环之前，z 是一个叶结点，最好情况下当然是循环过程一次都没有执行，此时这段代码的运行时间为`O(1)`；那么最坏情况呢？根据循环过程的代码，每次循环或者执行一次左旋、或者执行一次右旋操作，这两个操作都是常数级别的，并且操作结束之后，将会导致根节点到 z 的简单路径长度减一，因此我们很容易可以知道，最多经过 z 的初始高度的操作次数之后，循环将结束，而 z 的移动路径，也就是一条从根节点到 z 的简单路径，因此最坏情况下也就是 z 从叶结点一直移动到根节点，期望运行时间为`O(lgn)`。

所以最后整个过程的期望运行时间为上面两个部分的运行时间之和，即`Theta(lgn)`。

引理定义

TREAP_INSERT先执行一个查找，然后做一系列旋转。虽然这两种操作的期望运行时间相同，但他们的实际代价不同。查找操作从treap树中读取信息而不做修改。相反，旋转操作会改变treap树内的父结点和子节点的指针。在大部分的计算机上，读取操作要比写入操作快很多。所以我们希望TREAP_INSERT执行少量的旋转。后面将说明所执行旋转的期望次数有一个常数界。

为此，需要做一些定义，如图13-11所示。一棵二叉搜索树 T 的左脊柱（left spine）是从根节点到有最小关键字的结点的简单路径。换句话说，左脊柱是从根节点开始只包含左边缘的简单路径。对称的，T 的右脊柱（right spine）是从根节点开始只包含右边缘的简单路径。一条脊柱的长度是它包含的结点数目。

e. 考虑利用TREAP_INSERT插入结点 x 后的 treap T。设 C 为 x 左子树的右脊柱的长度，D 为 x 右子树的左脊柱的长度。证明：在插入 x 期间所执行的旋转的总次数等于 C + D。

这一个问题我们也可以通过非形式化的说明来解决。考察一下旋转操作，对于左旋来说，操作结果就是 x 的右孩子结点 y 接替了 x 的位置，同时 x 成了其结点 y 的的左孩子，而原来结点 y 的左孩子则成为了 x 的右孩子，因此，对结点 x 的一次左旋操作，其结果就是让结点 y 的左子树的右脊柱长度加一（增加了 x 结点）。同理对于右旋操作来说，结果就是让 y 结点的右子树的左脊柱长度加一。

回到题目，因为被插入结点 x 最开始左右子树均为nil，因此 C = D = 0，然后每执行一次左旋操作，C 的值加一，而每执行一次右旋操作，D 的值加一，因此当操作结束之后，C + D 的值也就是左旋和右旋的总次数。

性能分析

现在来计算 C 和 D 的期望值。不失一般性，假设关键字为1，2，…，n，因为只是将它们两两比较。

对 treap T 中的结点 x 和 y，其中`y != x`，设 k = x.key 以及 i = y.key。定义指示器随机变量

`X_(ik) = I{y`在`x`的左子树的右脊柱中`}`

f. 证明：`X_(ik) = 1`当且仅当`y.prio rity > x.prio rity, y.key < x.key`成立，且对于每个满足`y.key < z.key < x.key`的 z，有`y.prio rity < z.prio rity`。

证明：首先我们来证明正向推导过程。如果`X_(ik) = 1`，则意味着 y 在 x 的左子树的右脊柱中，因此有`y.prio rity > x.prio rity, y.key < x.key`，而对于满足`y.key < z.key < x.key`条件的 z结点，可以确定 z 必然在 y 的右子树中，所以`y.prio rity < z.prio rity`成立。

然后证明逆向过程。根据`y.prio rity > x.prio rity, y.key < x.key`可以得知，y 必然在 x 的左子树中。现在假设 y 不在 x 的左子树的右脊柱中，那么也就意味着 y 在 x 的左孩子结点的左子树中，那么我们很容易就可以发现，对于 x 的左孩子结点 z 来说，其满足`y.key < z.key < x.key`，但是却又有`y.prio rity < z.prio rity`，这与题设不符合，因此可知 y 必然在 x 的左子树的右脊柱中，才能使每个满足`y.key < z.key < x.key`的 z，有`y.prio rity < z.prio rity`。

综合上述过程，可以证明`X_(ik) = 1`当且仅当`y.prio rity > x.prio rity, y.key < x.key`成立，且对于每个满足`y.key < z.key < x.key`的 z，有`y.prio rity < z.prio rity`。

g. 证明：

`Pr{X_(ik)=1} = ((k-i-1)!)/((k-i+1)!) = 1/((k-i+1)(k-i))`

证明：由于每个结点的关键字和优先级之间是独立的，因此我们可以把所有结点按照关键字排序，则`X_(ik)`则涉及到从关键字从 i 到 k 的所有结点，由上面的假设关键字为1到n，可以得知`X_(ik)`涉及的结点个数为 k - i + 1。为了方便起见，我们把每个结点都用其关键字表示，由于序列已经按照关键字排序，因此`X_(ik)`对应的序列可以表示为T[i..k]。

根据上一题中的证明结果，`X_(ik) = 1`意味着在序列T[i..k]中，T[k]的优先级应该是最小的，而T[i]的优先级应该是第二小的。因为序列T[i..k]排列顺序是随机的，所以T[i..k]使得`X_(ik) = 1`成立的概率为：

`1/(k-i+1) * 1/(k-i) = 1/((k-i+1)(k-i))`

所以

`Pr{X_(ik)=1} = ((k-i-1)!)/((k-i+1)!) = 1/((k-i+1)(k-i))`

而对于上式中间的表达式的解释，我们可以理解为：对于序列T[i..k]，其元素排列所有可能顺序的总数为 (k - i + 1) 个元素的一个全排列，即 (k - i + 1)!；而当`X_(ik) = 1`时，则我们需要固定序列中的两个元素，其它元素仍然是可以随机排列的，这样，其可能顺序的总数为 (k - i + 1 - 2) 个元素的一个全排列，即 (k - i - 1)!。因此，最后概率即为`X_(ik) = 1`成立的排列数与总排列数的比值。

h. 证明：

`E[C] = sum_(j=1)^(k-1) 1/(j(j+1)) = 1-1/k`

证明：根据`X_(ik)`的定义可知，一个结点 x 的左子树的右脊柱的长度为：

`C = sum_(j=1)^(k-1) X_(jk)`

对上式两边取期望，可得：

`E[C] = sum_(j=1)^(k-1) E[X_(jk)] = sum_(j=1)^(k-1) Pr{X_(jk)=1}`

代入问题g中的证明结果，并稍作变换（令j = k - j），即可得到下式：

`E[C] = sum_(j=1)^(k-1) 1/(j(j+1))`

而`1/(j(j+1)) = 1/j - 1/(j+1)`，展开上面等号右边的和式，得：

`sum_(j=1)^(k-1) 1/(j(j+1)) = 1/1 - 1/2 + 1/2 - 1/3 + … + 1/(k-1) - 1/k = 1 - 1/k`

因此

`E[C] = sum_(j=1)^(k-1) 1/(j(j+1)) = 1-1/k`

得证。

i. 利用对称性证明：

`E[D] = 1-1/(n-k+1)`

证明：如果 y 在 x 的左子树中，有 y.key < x.key，而如果在 x 的右子树中，则有 y.key > x.key。因此，根据对称性，我们有：

`Pr{X_(ik)=1} = 1/((i-k+1)(i-k))`

`D = sum_(j=k+1)^n X_(jk)`

`E[D] = sum_(j=k+1)^n E[X_(jk)] = sum_(j=k+1)^n Pr{X_(jk)=1}`

`E[D] = sum_(j=1)^(n-k) 1/(j(j+1)) = 1-1/(n-k+1)`

所以原式得证。

j. 得出如下结论：当在一棵treap树中插入一个结点时，执行旋转的期望次数小于2。

证明：有了h和i中的结果，这一结论的得出也就是水到渠成了。执行旋转的总次数为 C + D，根据期望的线性性质，我们有：

`E[C+D] = E[C]+E[D] = 1-1/k+1-1/(n-k+1) = 2-1/k-1/(n-k+1)`

由于`0 < k <= n`，所以有`1/k > 0`且`1/(n-k+1) > 0`，所以

`E[C+D] = 2-1/k-1/(n-k+1) < 2`

得证。

结束

通过跟踪书中的a到j各个问题，逐步给出了Treap树的一些基本性质。对于问题b，过程仍需讨论和改进，但是b的结论我们是可以直接使用的。