题解 P6136

AnneKH · 2020-02-28 08:40:16 · 题解

Splay

伸展树（\operatorname{Splay\ Tree}），也叫分裂树，是一种二叉排序树，它能在 \operatorname O(\log n) 内完成插入、查找和删除操作。它由丹尼尔·斯立特 Daniel Sleator 和 罗伯特·恩卓·塔扬 Robert Endre Tarjan 在1985年发明的。

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

它的优势在于不需要记录用于平衡树的冗余信息。

• 和大部分平衡树一样，Splay_Tree 中每个节点的左子树所有节点都比它小，右子树所有节点都比它大。每个节点要维护以下信息：

  • 值（value）
  • 重复次数（count）
  • 子树大小（size）
  • 家长编号（mother）
  • 孩子编号（daughter_{0, 1}）

• 时间复杂度简单证明（直观感受一下）：

  • 如果数据随机，那么树一定平衡；
  • 如果数据不随机，那么每次将要访问的节点搬移至根，可应付不随机的数据。

• 考虑如何旋转。

  • 考虑将某一结点上旋。

      //旋转相关代码
      bool inline get_id(unsigned int const x) const {
          return tree[tree[x].mother].daughter[1] == x;
      }
      void const inline upto(unsigned int const x) {
          tree[x].size =
              tree[tree[x].daughter[0]].size + tree[tree[x].daughter[1]].size
              + tree[x].count;
      }
      void const inline connect
          (unsigned int const x, unsigned int const y, bool const id) {
          tree[x].mother = y, tree[y].daughter[id] = x;
      }
      void const inline rotate(unsigned int const x) {
          unsigned int const m(tree[x].mother), g(tree[m].mother);
          bool const id(get_id(x)), mid(get_id(m));
          connect(tree[x].daughter[!id], m, id), upto(m),
          connect(m, x, !id), upto(x), connect(x, g, mid);
      }

  • 那么将一个节点旋转到指定位置，就可以一直将这个节点上旋。然而这种做法可能会被毒瘤出题人卡掉。

  • 一种可行解是：

    • 如果节点 x、x 的家长、x 的祖父母在一条链上，则先旋转 x 的家长，再旋转 x；
    • 如果不在一条链上，则旋转两次 x。

      //旋转节点到指定位置代码
      void const inline splay(unsigned int const x, unsigned int root) {
          root = tree[root].mother;
          while (tree[x].mother not_eq root)
              if (tree[tree[x].mother].mother == root) rotate(x);
              else
                  if (get_id(x) == get_id(tree[x].mother))
                      rotate(tree[x].mother), rotate(x);
                  else
                      rotate(x), rotate(x);
      }
      void const inline Splay(unsigned int const x) {
          splay(x, root), root = x;
      }

旋转是 Splay_Tree 时间复杂度的保证，在每次操作后都尽量旋转。

以下是题目要求操作的实现。比较简单。可以略过直接看代码。

• 插入 value

  • 从根节点走到一个值与 value 相等的节点或空节点，将该节点的 count 增加一或新建一个节点。（在过程中将路径上所有 size 增加 1。）

• 删除 value

  • 从根节点走到值与 value 相等的节点，将该点 count 减少 1。（在过程中将路径上所有 size 减少 1。）

• 查询排名

  • 从根节点走下来，假如走到右子树，就将答案加上左子树大小与子树根节点 count 的值。

• 查询某排名的数。

  • 类似查询排名，当发现要查询的排名正好在当前节点中的话就返回。

• 查询 value 的前驱

  • 一种可行的方法是查询排名为 value 的排名减一的数。
  • 也可以不断逼近 value，更新答案。

• 查询 value 的后继

  • 同理查询前驱。

template<typename T = unsigned int>
class Balanced_Binary_Tree {
private:
    struct Point {
        T value;
        unsigned int count;
        unsigned int size;
        unsigned int daughter[2], mother;
        Point() { size = count = 0, mother = daughter[1] = daughter[0] = 0; }
        Point(T const value) {
            this->value = value,
            size = count = 1, mother = daughter[1] = daughter[0] = 0;
        }
    } tree[N + M + 1];
    unsigned int length, size, root;
    bool inline get_id(unsigned int const x) const {
        return tree[tree[x].mother].daughter[1] == x;
    }
    void const inline upto(unsigned int const x) {
        tree[x].size =
            tree[tree[x].daughter[0]].size + tree[tree[x].daughter[1]].size
            + tree[x].count;
    }
    void const inline connect
        (unsigned int const x, unsigned int const y, bool const id) {
        tree[x].mother = y, tree[y].daughter[id] = x;
    }
    void const inline rotate(unsigned int const x) {
        unsigned int const m(tree[x].mother), g(tree[m].mother);
        bool const id(get_id(x)), mid(get_id(m));
        connect(tree[x].daughter[!id], m, id), upto(m),
        connect(m, x, !id), upto(x), connect(x, g, mid);
    }
    void const inline splay(unsigned int const x, unsigned int root) {
        root = tree[root].mother;
        while (tree[x].mother not_eq root)
            if (tree[tree[x].mother].mother == root) rotate(x);
            else
                if (get_id(x) == get_id(tree[x].mother))
                    rotate(tree[x].mother), rotate(x);
                else
                    rotate(x), rotate(x);
    }
    void const inline Splay(unsigned int const x) {
        splay(x, root), root = x;
    }
public:
    Balanced_Binary_Tree() { size = length = 0; }
    void const inline Insert(T const x) {
        if (not size++) {
            tree[root = ++length] = Point(x), connect(root, 0, 0);
            return;
        }
        for (unsigned int register i(root); ++tree[i].size, true;) {
            if (tree[i].value == x)
                { ++tree[i].count, Splay(i); return; }
            else {
                bool id(tree[i].value < x);
                if (not tree[i].daughter[id]) {
                    tree[++length] = Point(x), connect(length, i , id),
                    Splay(length);
                    return;
                }
                else
                    i = tree[i].daughter[id];
            }
        }
    }
    void const inline Delete(T const x) {
        --size;
        for (
            unsigned int register i(root);
            tree[i].size--;
            i = tree[i].daughter[x > tree[i].value]
        )
            if (tree[i].value == x) {
                if (--tree[i].count) { Splay(i); return; }
                Splay(i);
                if (not tree[i].daughter[0])
                    { connect(root = tree[i].daughter[1], 0, 0); return; }
                if (not tree[i].daughter[1])
                    { connect(root = tree[i].daughter[0], 0, 0); return; }
                unsigned int j(tree[i].daughter[0]);
                while (tree[j].daughter[1]) j = tree[j].daughter[1];
                splay(j, tree[i].daughter[0]);
                connect(tree[i].daughter[1], tree[i].daughter[0], 1),
                upto(tree[i].daughter[0]),
                connect(root = tree[i].daughter[0], 0, 0);
                return;
            }
    }
    unsigned int inline Get_Ranking(T const x) {
        unsigned int r(1);
        for (unsigned int register i(root); i;)
            if (tree[i].value == x)
                { Splay(i); return tree[tree[i].daughter[0]].size + 1; }
            else
                if (tree[i].value < x)
                    r += tree[tree[i].daughter[0]].size + tree[i].count,
                    i = tree[i].daughter[1];
                else
                    i = tree[i].daughter[0];
        return r;
    }
    unsigned int inline Get_Rank(unsigned int const x) {
        unsigned int r(1);
        for (unsigned int register i(root); true;) {
            if (
                r + tree[tree[i].daughter[0]].size <= x
                and x < r + tree[tree[i].daughter[0]].size + tree[i].count
            ) { Splay(i); return tree[i].value; }
            else
                if (x < r + tree[tree[i].daughter[0]].size)
                    i = tree[i].daughter[0];
                else
                    r += tree[tree[i].daughter[0]].size + tree[i].count,
                    i = tree[i].daughter[1];
        }
    }
    T inline Get_Less(T const x) {
        T r; unsigned int register li;
        for (unsigned int register i(root); i;)
            if (tree[i].value >= x) li = i, i = tree[i].daughter[0];
            else r = tree[li = i].value, i = tree[i].daughter[1];
        Splay(li);
        return r;
    }
    T inline Get_Greater(T const x) {
        T r; unsigned int register li;
        for (unsigned int register i(root); i;)
            if (tree[i].value <= x) li = i, i = tree[i].daughter[1];
            else r = tree[li = i].value, i = tree[i].daughter[0];
        Splay(li);
        return r;
    }
};