伸展树

描述

一种保证从空树开始任意连续M次对树的操作最多花费\(O(M\log{N})\)时间的树

不存在不好的输入序列

基本想法： 当一个 Node 被访问后， 就要经过一系列 AVL 树的旋转被推到根上

伸展(Splayling)

伸展的方法类似于旋转, 在旋转如何实施上增加一些选择的余地

之子形

一子形

伸展树的操作