伸展树学习笔记之双层伸展
一. 双层伸展
- 构思精髓：向上追溯两层，而非一层。
- 反复考察祖孙三代：g=parent(p),p=parent(v),v
- 根据它们的相对位置，经两次旋转使得v上升两层，成为子树根。
二. 子孙异侧
- 与AVL树双旋完全等效
- 与逐层伸展别无二致
三. 子孙同侧
四. 点睛之笔
第一次旋转在祖父的位置上进行，而非父亲的位置。
step1:
step2:
step3:
step4:
step5:
step6:
step7:
step8: 最终，节点1被延伸到树根，整个树的高度大约为原来的一半。
结论：在一棵退化成单链的伸展树中访问其最深的节点，经过伸展后树高大约为原先的一半。
- 访问任何一个节点，该节点所对应的那条路径长度会折减一半（类似于含羞草）
- 最坏情况不会持续发生
- 单趟伸展操作所需要的时间，不超过O(logn)