伸展树
逐层伸展 宽松平衡
局部性
Locality： 刚被访问过的数据，极有可能很快地再次被访问—>信息处理中常见 //BST
BST：刚刚被访问过的节点，极有可能很快的再次被访问
下一将要访问的节点，极有可能就在刚被访问过的节点的附近
连续的m次 查找（m » n =|BST|） ,采用AVL共需要O（mlogn）时间
个人理解：在足够长的时间中，把被访问次数足够多的节点放到前面，增加访问效率
逐层伸展
节点v一旦被访问，随即转移至树根
—>通过旋转的方法移动二叉树的节点。
zig(顺时针)、zag(逆时针)
一步一步往上爬
自下而上，逐层单旋
zig( v->parent)
zag( v->parent)
直到v最终被`推送`至根 ### 最坏情况 旋转次数呈`周期性`的`算术级数`演变：每一周期累计`\Omega \left ( n^{2} \right )` 分摊`\Omega \left ( n\right )`---->Latex公式编辑器 ### 双层伸展 构思精髓：向上追溯`两层`，而非`一层` 反复考察`祖孙三代`：g=parent(p),p=parent(v),v 根据他们的相对位置，经`两次旋转`使得v上升两层，成为（子）树根
zig-zag zag-zig 与AVL树双旋完全等效 与逐层伸展别无二致
zig-zig zag-zag –>先移动祖父节点，然后移动父节点