（treap树）如果将一个包含n个元素的集合插入到一棵二叉搜索树中，所得到的树可能会想当不平衡，从而导致查找时间很长。然而，随机构造二叉搜索树是趋向于平衡的。因此，一般来说，要为一组固定的元素建立一棵平衡树，可以采用的一种策略就是先随机排列这些元素，然后按照排列的顺序将它们插入到树中。
如果没法同时得到所有的元素，应该怎样处理呢？如果一次收到一个元素，是否仍然能用它们来随机建立一棵二叉搜索树？
我们通过考察一个数据结构来证明回答这个问题。一棵treap树是一棵更改了节点排序方式的二叉搜索树。下图显示了一个例子。通常，树内的每个节点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树是会有帮助的。假设将已有相应关键字的节点x1,x2,...,xn插入到一棵treap树内。得到的treap树是通过将这些节点以它们的优先级（随机选取的）顺序插入到一棵正常的二叉搜索树形成的，即xi.priority<xj.priority表示xi和xj之前被插入。
a.证明：给定一个已有相应关键字和优先级（互异）的节点x1,x2,....,xn组成的集合，存在唯一的一棵treap树与这些节点相关联。
b.证明：treap树的期望高度是)
，因此在treap内查找一个值所花的时间为。让我们看看如何将一个新的节点插入到一个已存在的treap树中。要做的第一件事情就是将一个随机的优先级赋予这个新节点。然后调用称为TREAT-INSERT的插入算法，其操作如下图。
c.解释TREAP-INSERT是如何工作的。说明其思想并给出伪代码。（提示：执行通常的二叉搜索树插入过程，然后做旋转来恢复最小堆顺序的性质。）
d.证明：TREAP-INSERT的期望运行时间是。
TREAP-INSERT先执行一个查找，然后做一系列旋转。虽然这两种操作的期望运行时间相同，但它们的实际代价不同。查找操作从treap树中读取信息而不做修改。相反，旋转操作会改变treap树内的父节点和子节点的指针。在大部分的计算机上，读取操作要比写入操作快得多。所以我们希望TREAP-INSERT执行少量的旋转。后面将说明所执行的旋转期望次数有一个常数界。
为此，需要做一些定义，如下图所示。一棵二叉搜索树T的左脊柱（left spine）是从根节点到有最小关键字的节点的简单路径。换句话说，左脊柱是从根节点开始只包含左边缘的简单路径。对称地，T的右脊柱（right spine）是从根节点开始只包含右边缘的简单路径。一条脊柱的长度是它包含的节点数目。
e.考虑利用TREAP-INSERT插入节点x后的treapT。设C为x左子树的右脊柱的长度，D为x右子树的左脊柱的长度。证明：在插入x期间所执行的旋转的总次数等于C+D。现在来计算C和D的期望值。不失一般性，假设关键字为1,2，...,n，因为只是将它们两两比较。
对treapT中的节点x和y,其中
，设k=x.key以及i=y.key。定义指示器随机变量
Xik=I{y在x的左子树的右脊柱中}
f.证明：Xik=1当且仅当y.priority>x.priority，y.key<x.key成立，且对于每个满足y.key<z.key<x.key的z，有y.priority<z.priority。
g.证明：
h.证明：
i.利用对称性证明：
j.得出如下结论：当一棵treap树中插入一个节点时，执行旋转的期望次数小于2。
