(a1)伸展树：逐层伸展
看清 zig / zig-zig / zig-zag 三态旋转，掌握均摊 O(log n) 的势能证明
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
(a1)伸展树：逐层伸展
看清 zig / zig-zig / zig-zag 三态旋转，掌握均摊 O(log n) 的势能证明
宽松平衡
逐层伸展把目标节点搬到根后，树不会变成 AVL 那种严格平衡，而是处于一种「松但不散」的状态——这就是宽松平衡。它保证树高仍是 O(log n)，但允许更大的形变。
每下一级人数至少按常数比缩小，层级总数被锁死在 log n
局部性
上页说伸展树是宽松平衡——不严格控树高，只把刚访问的节点推到根。凭什么是好策略？这依赖一个现实规律：几乎所有程序都有局部性。它是伸展树摊还分析的前提，也是与严格平衡树的分水岭。
正在用的摊在桌面（根），翻过的堆在旁边（近），很久没碰的束之高阁（叶）
自适应调整
前页讲到局部性：刚被访问的节点很可能再次被访问。伸展树如何兑现这一性质？靠的就是访问即调整——每次操作结束后，树形都会按本次访问重新组织，让热点节点上浮、冷门节点下沉。
管理员把频繁被借的书逐步前移，下次取书更快；冷门书自然退到深处
逐层伸展
访问一个节点后要把它移到根。最直觉的做法——每次往上旋一层、转完为止——听起来天经地义。但这条朴素的路，其实藏着 O(n) 的陷阱。
楼越深耗时越长；关键是上面几级在这次动作里完全没动，全靠一次次补
实例
查到了 7 号节点，但它还远在树的下层。下次想更快命中它，就必须把它一步一步提到根。每往上爬一层，就要做一组对应旋转——这就是「逐层伸展」的核心思路。
直上一级是 zig；同侧像跨两级，异侧只能走 Z 字绕弯
一步一步往上爬
访问一个节点后，伸展树要把它送到根。但树那么高，怎么送？答案是：每次只看局部两层，一步一步往上爬。
zig=单步，zig-zig=同向连跳两阶，zig-zag=转角跨两阶
最坏情况
上一页我们用逐层旋转把小节点一步步送上了根，方法直观又简单。但简洁是有代价的——某些访问顺序会让树严重失衡，单次操作最坏退化到 O(n)。
借书顺序不好时，热门书会一直沉到末端，每次找它都要翻整排
本节要点
- ✓机制：每次一层旋转，累计 log n 步上移
- ✓代价：长链最坏可退化到单次 O(n)
- ✓兜底：势能均摊下仍是 O(log n)
- ✓本质：用访问热度重塑树形
- ✓取舍：放弃严格平衡换取自调整
课后思考
先合上笔记自己想，再点开参考答案对思路——三个问题对应三个层次。
参考答案单次操作可能把整条路径翻一遍；但被访问过的节点都"付过费"，下次再访就近了。均摊看的是总代价除以操作次数——"前人栽树，后人乘凉"。
参考答案热点键被访问后升到根部附近，再次访问路径极短；AVL/红黑树每次都得走 O(log n)。偶发冷数据会触发大量旋转，但热点更快，整体仍快。
参考答案可以——反复交替访问根与同一叶子，两者反复互换位置。说明均摊保证依赖"访问具有时间局部性"，刻意构造的对抗序列能打破它。