（转）伸展树

伸展树是平衡二叉搜索树的一种形式，相对于AVL树，伸展树的实现更为简洁。伸展树无需时刻保持全树的平衡，但是能够保持分摊意义上的高效率。伸展树不需要对基本的二叉树节点结构做任何附加的要求或改动，也不需要记录平衡因子或高度之类的额外信息，故适用范围比AVL树广。

伸展树基于的一种启发式思想，数据局部性。即：
（1）刚刚被访问过的节点，极有可能在不久之后再次被访问到。
（2）将被访问的下一个节点，极有可能就处于不久之前被访问过的某个节点的附近。

简易伸展树采用逐层伸展的策略，就是刚被访问过的节点经过一层层的旋转，达到根节点。但是这种策略有致命的缺陷，在最坏的情况下单次访问时间高达O(n)。这个问题的根源可以解释为：在持续访问的过程中，树高依算术级数逐步从n-1递减到n/2，然后在逐步递增回n-1。

因此伸展树采用的伸展策略是双层伸展。双层伸展基于节点的相对位置，分了三种情况：
（1）zig-zig/zag-zag：双层优于逐层的关键所在。
（2）zig-zag/zag-zig
（3）zig/zag
双层伸展策略既可以将v推至树根，亦可令对应分支的长度以几何级数（大致折半）的速度收缩。

伸展树的单词操作均可在分摊的O(logn)时间内完成。