CSP-S复习计划-Splay

写一种数据结构,来维护一些数,其中需要提供以下操作:

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

这就是伸展树的基本操作,也是伸展树名字的由来(这里讲算法不讲历史)。
重要的的函数有RotateSplayDel其他的都是一些树上操作罢了。
代码如下:

发表评论

电子邮件地址不会被公开。 必填项已用*标注