[Dr.Lib]Note:Data Structures – Bottom-up SPLAY

Let us play!

Let u splay!

 

BST 平均 O(logn)

Treap 期望 O(logn)

Splay 均摊 O(logn)

AVL 严格 O(logn)

SBT 严格 O(logn)

AVL不大指望能在赛场写出来,SBT在绝大多数时候是个不错的选择,Treap…嗯……但偏偏Splay被人看成是BST中的万金油……为什么呐?

Splay一个最大的特点就是:每一个操作都要splay一下……除此之外没了……

Splay

splay操作的作用就是把某一节点旋转到根,以加快之后的访问速度。它还可以在旋转过程中维持树的基本平衡。

  1. zig: 当目标节点是根节点的 左子节点 或 右子节点 时,进行一次zig,将目标节点调整到根节点的位置。
    709px-Splay_tree_zig.svg
  2. zig-zig:当目标节点是根节点的 左(右)子节点的左(右)子节点 时,进行一次zig-zig,将目标节点调整到根节点位置。
    Zigzig
  3. zig-zag:当目标节点是根节点的 左(右)子节点的右(左)子节点 时,进行一次zig-zag,将目标节点调整到根节点位置。
    Zigzag

 

重复这几种操作直到目标节点为根。

一次zig、zig-zig、zig-zag又可以分解为几次单旋。

Search/Insert/Rank/Select

与BST相同,只不过记得把插入的节点Splay到根。

Join

作用是把两棵子树S1,S2连成一个Splay,其中S1中所有元素小于S2。

先找到S1中的最大节点x,Splay到S1的根,再把x的右子树链接到S2。

Delete

先找到目标节点,Splay到根,执行Join操作即可。

代码