（随机构建二叉搜索树中的平均节点深度）在本题中 ，要证明有n个节点的一棵随机构建二叉搜索树中的节点平均深度为O(lgn)。
定义一棵二叉树T的路径总长度（total path length）P(T)为T中所有节点x的深度之和，对每个节点x的深度表示为d(x,T)。
a.证明：T中的一个节点平均深度是
因此，我们希望进一步证明P(T)的期望值为O(nlgn)。
b.设TL和TR分别表示数T的左子树和右子树，证明：如果T有n个节点，则
P(T)=P(TL)+P(TR)+n-1
c.设P(n)表示有n个节点的随机构造二叉搜索树的平均路径长度，证明：
d.说明如何将P(n)重写为：
e.对于随机快速排序，试证明结论：P(n)=O(nlgn)。
在快速排序的每次递归调用时，总要选择一个随机划分元来为待排序的元素集合进行划分。二叉搜索树的每个节点都是对以该节点为根的子树中所有元素进行划分。
f.请给出快速排序的一种实现，使快速排序中对一组元素的比较与将这些元素插入一棵二叉搜索树中所需的比较恰好相同。（这些比价的次序可以不同，但出现的比较一定要一样。）
