定义

Splay 是一种可以自我调节的二叉搜索树。它在 $\Theta(\log n)$ ​ 的均摊时间内执行基本操作,例如插入,查找和删除。对于许多非随机操作序列,Splay 比其他搜索树表现更好。

核心操作

我们提到 Splay 可以 “自我调节”,这一性质使得它能维持树形结构,保证复杂度。自我调节分为两部分:旋转 (rotate),以及伸展 (splay)。

旋转

伸展

实际运用

作为二叉搜索树,它能完成所有二叉搜索树都能完成的基本操作。当然,它也可以作为区间树完成诸如区间翻转的操作,正是这一性质使得它可以作为 Link Cut Tree 的辅助树。

代码

普通平衡树

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

  1. 插入 $x$ 数
  2. 删除 $x$ 数(若有多个相同的数,因只删除一个)
  3. 查询 $x$ 数的排名(排名定义为比当前数小的数的个数 $+1$。若有多个相同的数,因输出最小的排名)
  4. 查询排名为 $x$ 的数
  5. 求 $x$ 的前驱(前驱定义为小于 $x$,且最大的数)
  6. 求 $x$ 的后继(后继定义为大于 $x$,且最小的数)

区间翻转

点击查看这道题目的 详细描述

  1. oyyj603470138
    Sep 01, 2018

    这题还好吧。。

    Reply
    • kal0rona
      Apr 04, 2019

      博主在机房调了一天。。。

      Reply