a、归纳法：
基本情况是树中没有节点，空树明显是唯一的；假设一棵含有k-1（k>=1）个节点的treap是唯一的，当插入第k个节点后，拥有最小优先级的节点x肯定是该treap的根节点，并且所有关键字小于key[x]的节点都在x左子树，所有关键字大于 key[x] 的节点都在x的右子树,也就是说根及根的左右子树都是唯一确定的，因此归纳得出含有k个节点的treap也是唯一的(因为左右子树的节点数均小于或等于k-1,根据归纳假设左右子树也是唯一的treap)
b、思路：一个n节点的treap等价于在n个节点上随机构造的二叉查找树。回想一下，n个节点插入到treap并给它们指定一个优先级等同于将n个节点按照某个指定的优先级递增的顺序依次插入到二叉查找树中。因此，如果我们随机地给这n个节点指定优先级，我们就得到了n个优先级大小的随机序列，这和随机排列n个元素再将它们插入到树中是一样的。另外，n个节点二叉查找树其高度明显为?(lg n)，因此，treap的期望高度为Θ(lg
n)，在treap内查找一个值所花的时间为Θ(lg n)。
c、根据提示： TREAP-INSERT 的思路就是先执行通常的二叉查找树插入程序，然后做旋转来恢复最小堆顺序的性质。
TREAP-INSERT (T, x)
TREE-INSERT (T, x)
while x ≠ root[T] and priority[x] < priority[p[x]]
do if x = left[p[x]]
then RIGHT-ROTATE (T, p[x])
else LEFT-ROTATE (T, p[x])d、TREAP-INSERT首先执行通常的二叉查找树的TREE-INSERT然后再执行一系列的旋转操作来恢复最小堆性质。通常的二叉查找树插入算法将新节点插入树中作为新的叶子节点，因此Treap的插入操作的时间复杂度和随机构造的二叉查找树的高度成正比，期望运行时间为O(lg n)。最大旋转次数发生于当新插入节点的优先级小于所有树中已有节点的优先级的情况下，此时，它需要从叶子节点一直做旋转操作到根节点，因此旋转次数的上界为随机构造的二叉查找树的高度，为O(lg
n)（从后面几问可以看出，O(lg n)只是个很松散的上界）。因为每次旋转所需的时间为常量级，因此旋转操作的期望时间为O(lg n)。所以TREAP-INSERT操作的期望时间为O(lg n+lg n)=O(lg n)
e、通过执行的旋转次数来证明。
归纳法：基本情况是当x是作为一个叶子节点插入，此时不需要执行旋转操作，C+D=0。假设执行k-1次旋转后C+D=k-1,那么执行了k次旋转（假设为右旋）后，通过对二叉查找的右旋操作观察可以看出：不妨假设y为x的父节点，并且假设x是y的左孩子。当执行了一次右旋后，y变成x的右孩子，并且之前x的右孩子变成y的左孩子。也就是说，旋转前x的右子树的左脊柱往上附到了y,因此它的脊柱长度增加1。x的左子树不受右旋操作的影响。同理，左旋操作也是类似的。因此，每当执行完一次旋转操作后，C+D就增加l,当执行了k次旋转后，C+D=k.从而证明了我们的假设。
f、X[i,k]=1{y是（T内）x左子树的右脊柱}
要证明“X[i,k]=1 当且仅当 （1）priority[y]> priority[x],（2）key[y]<key[x],并且（3）对于每个满足 key[y] < key[z] < key[x] 的z, 有priority[y] < priority[z]”
1》证明：如果 （1）priority[y] > priority[x],（2）key[y]< key[x],并且（3）对于每个满足 key[y] < key[z] < key[x] 的z, 有priority[y] < priority[z]，那么 X[i,k]=1。
反证法：假设X[i,k]=0，也就是说y不是（T内）x左子树的右脊柱，那么y可能是下面三种情况之一：
1、y在x的右子树。则有key[y]> key[x],这将和（2）矛盾；
2、y不在x的任何子树中。那么x和y一定有某个共同祖先z.由于key[y]< key[x]，我们知道y在z的左子树，x在z的右子树，并且key[y] < key[z] < key[x]。由于x、y是在z的子树中，因此priority[z] < priority[x]并且priority[z] < priority[y],这与（3）矛盾；
3、y在x的左子树，但是y不在x的左子树的右脊柱中。这意味着在x的左子树中存在y的某个祖先节点z,即y在z的左子树，那么有key[y] < key[z] < key[x]，既然z是y的祖先，那么priority[z] < priority[y],这与（3）矛盾。
综上，三种可能情况都导致与已知条件冲突，因此假设不成立，即X[i,k]=1成立。
2》证明：如果X[i,k]=1，那么（1）,(2)和（3）成立。
如果X[i,k]=1，那么y位于（T内）x左子树的右脊柱，既然y在x的子树中，很明显 priority[y] > priority[x]，（1）得证；又y在x的左子树，故key[y]< key[x]，（2）得证；下面用反证法证明（3）。
假设：当X[i,k]=1并且存在某个z使得当 key[y] < key[z] < key[x] 时 ，有 priority[z] < priority[y]。换句话说，z比y先插入Treap中。下面有三种情况满足条件 key[z] < key[x]：
1、z在x的左子树的右脊柱中。根据假设X[i,k]=1可知y也在x的左子树的右脊柱中，因为z比y先插入到x的左子树的右脊柱中，那么y必须插入到z的右子树中，而这与key[y]< key[z]矛盾。
2、z在x的左子树，但是z不在x的左子树的右脊柱中。这意味着z位于x的左子树的右脊柱中的某个节点z‘的左子树中。根据假设X[i,k]=1可知y在x的左子树的右脊柱中，和情况1类似，因为z比y先插入到Treap中,当y被插入到x的左子树的右脊柱中时，y也必须插入到z‘的右子树中，这与key[y]< key[z]矛盾，。
3、z不在x的子树中。那么z和x一定有某个共同祖先z‘.由于key[z]< key[x]，我们知道z在z‘的左子树，x在z‘的右子树，并且key[z] < key[z‘] < key[x]，根据条件又有 key[y] < key[z] < key[z‘]< key[x] ,因此y不能被插入到x的子树中，这与假设条件“y在x的左子树的右脊柱中”矛盾。
综上，当X[i,k]=1时，不存在这样的节点z，使得 key[y] < key[z] < key[x] 时 ，有 priority[z] < priority[y]。反之，命题得证，即：如果X[i,k]=1，那么（1）,(2)和（3）成立。
g、在之前的证明中，我们已经得出结论：X[i,k]=1当且仅当y跟x之间节点的的优先级是按照某种特定次序的。我们已经在(f)中证明了，X[i,k]=1只依赖于x,y优先级的相对次序，并且对所有的满足 key[y] < key[z] < key[x] 的z, 有priority[y] < priority[z]。假设所有节点的关键字是从{1,2...n}取出,本问题中X[i,k]=1的关键字介于i,i+1,i+2....k-1,k，总共有(k?i+1)!种优先级排列数，其中，X[i,k]=1的排列数是那些i为最小优先级，k为第二小优先级，其他k-i-1个优先级可以是任意排序,总共有(k?i-1)!种优先级排列数。因此，X[i,k]=1的概率为(k?i?1)!/(k?i+1)!
= 1/(k?i)(k?i+1).
h、对于某个关键字为k的节点x,E[C]是在x的左子树的右脊柱的节点数量的期望值，这等价于所有对i的随机变量X[i,k]的期望值的和。当节点i ≥ k时，y不在x的左子树的右脊柱中，X[i,k]=0，因此我们只需考虑i<k:
i、不妨设T为按照给定的关键字序列依次插入生成的Treap，按照关键字逆序的次序将节点依次插入到另外一个Treap中，这样得到了T的一个镜像T‘。考虑T中关键字为k的节点x，那么在T’中它的映射节点的关键字为n-k+1。T中节点x的右子树的左脊柱的长度就是T’中x的左子树的右脊柱的长度。在（h）中，我们已经证明T中一个节点x的左子树的右脊柱的期望长度为1-1/k,因此在T‘中一个节点xd
右子树的左脊柱的期望长度为1-1/(n-k+1),即