（摊还加权平衡树）考虑扩充普通二叉搜索树，为每个节点x增加属性x.size，此属性给出了根为x的子树中关键字的数量。令
是
之间的一个常数。当x.left.size
*x.size，且x.right.size *x.size时，我们称节点x是平衡的。如果树中每个节点都是平衡的，则称树整体是平衡的。G.Varghese提出了如下摊还方法来维护加权平衡树。
a.在某种意义上，一棵1/2平衡树达到了极限的平衡，给定任意一棵二叉搜索树中的一个节点x,证明：如何重建以x为根的子树，使得它变为1/2平衡的。你的算法的运行时间应该为)
，可以使用O(x.size)的辅助空间。
b.证明：在一棵n个节点的平衡二叉搜索树中执行一次搜索操作的最坏情况时间为O(lgn)。
对于本题的剩余部分，假定常数严格大于1/2。假设你实现的INSERT和DELETE算法与普通n节点二叉搜索树的算法是一样的，差别仅在于，如果发现树中任何节点不再是平衡，则在最高的不平衡节点，对以它为根的子树执行“重建”，使其变为1/2平衡的。
我们用势能法分析此重建方法。对于二叉搜索树T中的一个节点x,定义：
定义T的势函数是：
其中，c是一个足够大的常数，它依赖于。
c.证明：任意二叉搜索树的势都是非负的，1/2平衡树的势为0.
d.假定m个单位的势够支付重建m节点子树的代价，相对于来说，c应该多大才能使得重建一棵非平衡的子树的摊还时间为O(1)。
e.证明：在一棵n节点的平衡树中插入一个节点或者删除一个节点的摊还时间为O(lgn)。
