伸展树

原理

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

操作

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

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

术语“左旋”、“右旋”

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

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

术语“双旋”、“单旋”

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

实现

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

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

常见问题

Rotate

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

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

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


最后更新: 2020年1月9日