伸展树¶

原理¶

伸展树的操作实际上是重要节点上浮的过程。

操作¶

伸展树实际上有三种操作以及这三种的镜像操作：zig, zig-zig, zag-zag。

分别对应上浮一层，同侧上浮两层，异侧上浮两层的双旋操作。

术语“左旋”、“右旋”¶

左旋是指节点x以右子为轴的下沉操作，同时也是右子的上浮过程。

右旋是指节点x以左子为轴的下沉操作，同时也是左子的上浮过程。

术语“双旋”、“单旋”¶

只有双旋是时间复杂度均摊O(nlogn)的，一般而言，双旋的层数要少于单旋层数

实现¶

编程经验表明，复杂的树结构，不要使用C++结构实现； 将节点的性质拆开维护。

init();  // 清空树
assign(&r, father, value);  // 以父节点和值初始化节点
rotate(x, kind);  // 对节点x进行左旋或者右旋
splay(x, goal);  // 将节点x旋转到goal节点下方，处理根节点的变化
insert(value);  // 插入值为value的元素
prev(x); nxt(x);  // 前驱后驱节点

常见问题¶

Rotate¶

先判定x节点的父节点旋转类型比较容易，因为是自上而下的思维方式。

错误操作：查询前驱后驱不Splay到根节点¶

所谓站得高看得远，因为把一切节点都踩在脚下； 如果不把所有节点踩在脚下，就不知道头上是否有节点更接近当前节点。