平衡树(Splay) artalter级服务:第二弹——插入，删除，查询

0.前言

今天有奥赛课，所以我又回来了

今天会把普通平衡树的操作讲完

1.插入

首先，在splay中，是不会有权值（也就是平衡树排大小的关键字）重复的结点的。取而代之的，是表示这个值出现次数的附加值cnt.

插入操作可以分为几种情况：

1.平衡树中什么也没有，这个时候我们只要新建第一个结点，并把它设为根节点就可以啦。

2.平衡树中已经出现过了这个权值。我们找到这个权值所在的位置，把这个结点的size值和cnt值都加一即可

3.这个权值在平衡树中还没有出现过。我们找到这个权值所应该在的位置，并在这个位置上新建一个结点，并把size值和cnt值都初始化为1

2,3的最后，都要把找到或新建的结点旋转到根节点

如何找出要插入到权值所应该在的位置？

我们从根结点往下找，判断要插入的权值和当前结点权值的大小。如果大于当前结点，就去它的右子树，否则就去它的左子树，直到两个权值相等或当前结点不存在

建立新结点的函数代码

void nowPoint(int val, int fa, int nxt) //新建一个权值为val，是fa结点的nxt孩子的结点
{
    tot++;
    fa(tot) = fa, size(tot) = cnt(tot) = 1, val(tot) = val;
    son(fa, nxt) = tot;
}

插入函数的代码

void insert(int val) //插入一个值为val的数
{
    if (root == 0)
    {
        nowPoint(val, 0, 1);
        root = tot;
        return;
    }

    int now = root;//查找部分在下面查找部分有比较详细的注释来解释
    while (1)
    {
        size(now)++;//让所有子树包含val结点的结点size值加1
        if (val(now) == val)
        {
            cnt(now)++, size(now)++;
            splay(now,root);
            return;
        }
        int nxt = val(now) < val, son = son(now, nxt);
        if (!son)
        {
            nowPoint(val, now, nxt);
            splay(tot, root);
            return;
        }
        now = son;
    }
}

2.删除

接下来就是splay最恶心最容易出锅的地方了（至少对我来说是这样）

什么是删除?

我以前听过一句话：一个人一生会经历三次死亡。第一次是生理上的死亡，第二次是最后一个认识你的人的死亡，第三次是所有能证明你存在的事物的消失。

在删除操作上也是同理：如何证明一个点被删除了？我们只要让它不是其他任何一个点的父节点,左孩子和右孩子就可以了。

在删除之前，我们首先要实现一个函数：find()。它的功能是查找一个权值为val的结点的编号,并把它旋转到根节点。如果不存在，就返回0

插入中有类似的代码，我就不再过多解释了

查询函数的代码

int find(int val)//查找val值对应的编号并旋转到根节点
{
    int now = root//从根结点向下查找
    while (1)
    {
        if (!now)//结构体中的值默认为0.如果now值为0，说明查找到了一个不存在的结点，也就是说这个权值在以前并没有被插入过，因此我们可以直接返回0
            return 0;
        if (val(now) == val)//如果有我们查到了这个权值
        {
            splay(now, root);//就把这个权值对应的结点旋转到根节点
            return now；//返回这个结点对应的编号
        }
        int nxt = val(now) < val, son = son(now, nxt);//如果val(now)<val,val对应的结点一定在右子树中，而此时val<val(now)的返回值恰好为1，也正表示右孩子
        now = son;
    }
}

我们进行删除操作的第一步，就是find一下val的编号。如果需要删除一个不存在的值，那么直接退出。

在find中，我们已经把val旋转到了根节点。现在，比val小的数都在根节点的左子树，比find大的数都在根节点的右子树。

我们可以把删除操作分成以下几种情况。

1.val结点出现过多次，我们只把它的cnt值和size值-1就可以了

2.val既没有左子树，也没有右子树，此时整棵树中只有val一个数，此时我们直接把root赋为0，也就是整颗树还没有结点的初始状态

3.val有左子树，但没有右子树。我们直接把val的左结点的父亲暴力改成0结点，把val的左结点暴力改成根结点就可以了。现在，val不是根节点，无法被直接选择，也无法由其他任何一个结点所遍历到，那么它就相当于被删除了。就像这样

图中原来的1号结点实质上已经被删除了（ 但是编号并没有被回收 ）

4.val有右子树，但没有左子树，此时同2

5.val既有左子树，又有右子树

我们此时找出val的左子树中最大的一个点pos，把它移动到根节点。

那么此时pos的左子树为之前val除pos以外的左子树（pos为之前val左子树中的最大值，因此在旋转的过程中它不会有左孩子，只有在倒数第二部它旋转到了val的左孩子，再次旋转时val就会变成pos的右孩子），右子树为val和它以前的右子树（pos是小于val的最大的结点，显然没有一个结点的权值在大于pos而小于val,因此val不可能有左孩子）。

我们在暴力把val的右孩子和pos连在一起，val就相当于被孤立了。我们放图来演示一下这个过程：

开始时

pos旋转到了val的左孩子

pos旋转到了根节点

val被删除了

删除之后，记得更新pos结点的size值

删除函数的代码

void delet(int val)//删除权值为val的结点
{
    int now = find(val);
    if (!now) return;
    if (cnt(now) > 1)//第一种
    {
        cnt(now)--, size(now)--;
        return;
    }
    if (!ls(now) && !rs(now))//第二种
    {
        root = 0;
    }
    else if (!ls(now))//第三种
    {
        root = rs(root);
        fa(root) = 0;
    }
    else if (!rs(now))//第四种
    {
        root = ls(root);
        fa(root) = 0;
    }
    else//第五种
    {
        int pos = ls(now);
        while (rs(pos))pos = rs(pos);//找出val的左子树中权值最大的结点pos

        splay(pos, root);//把pos旋转到根结点
        connect(rs(now), pos, 1);//暴力覆盖掉val的痕迹。
        pushup(pos);//因为有connect，所以要更新pos的值
    }
}

3.查询一个数的排名

首先给出一个数val的排名的定义：小于val的的数的个数+1

由定义，可以给出一个十分简洁的代码：

int Rank(int val)//查询val的排名
{
    int k = find(val);
    int x = size(ls(k)) + 1;
    return x;
}

由于我们使用了find，现在val结点是根结点，那么显然所有比val小的数都在val的左子树里，val的排名自然就等于它左子树的大小+1

然而，这样就可以了吗？

不行！

这样做只能查询一个在树中的数的排名

稍作修改后，我们可以得到这样一份代码：

int Rank(int val)//查询val的排名
{
    insert(val);
    int k = find(val);
    int x = size(ls(k)) + 1;
    delet(val);
    return x;
}

我们先把这个数插入，在查询完成之后把这个数删除。这样就能查询任何数的排名了。

现在总可以了吧！

还是不行！

还记得我在删除操作是说的吗？删除操作并不会回收编号，也就相当于不会回收空间。

在空间开销比较小时，这样做并没有什么问题。但是在树套树 \(o(n\log n)\)的空间复杂度下，如果还用这种肆意挥霍空间的方式，就相当于在数百万的结构体空间上再乘个 20倍。在那道题2中，我采用这种写法，经测试，需要的结构体空间可能在 数千万 。更何况一个结构体的空间占用可能是普通int型的 10 倍！

因此，我采用这种写法

int Rank(int val)
{
    int now = root, s = 0; //s存的是小于val的数的个数
    while ( now )
    {
        if (val(now) == val)
        {
            splay(now,root);
            return size(ls(now)) + 1;
        }
        if (val(now) < val)
        {
            s += size(ls(now)) + cnt(now);//递归的思想，在进入右子树之前，我们先把左子树和根的大小加上，接着进入右子树，就像是进了另一个平衡树
            now = rs(now);
        }
        else
        {
            now = ls(now);
        }
    }
    return s + 1;
}

虽说又臭又长，但总算能省点空间

4.查询第k小数

查询第k小数的代码就像是查排名代码的递归思想的延伸。

k这个排名就像是一个必须要缴够的费用，你每进入一颗右子树，您都可以上缴一个左子树和一个根结点的次数的费用。

当您要找的排名大于一个结点左子树的大小，而小于左子树的大小加它本身，那么这个结点就是排名第k大的数

int aRank(int k)
{
    int now = root;
    while ( 1 )
    {
        int used = size(now) - size(rs(now));//used表示的是当前子树除右子树外的大小
        if (k > size(ls(now)) && k <= used)
        {
            break;
        }
        if (k >= used)
        {
            k -= used;
            now = rs(now);
        }
        else
        {
            now = ls(now);
        }
    }
    splay(now, root);
    return val(now);
}

5.查询前驱

前驱就是 小于一个数 的最大的数

我们设一个ans,ans的初值为极小值

老套路，如果当前结点比所给值小，且比ans大，那么我们更新ans,并且去它的右子树，看看还有没有比当前结点大却比所给值小的结点。否则就去左子树，缩小当前结点的值。

代码和之前大同小异

int lower(int val)
{
    int ans = -2147483647;
    int now = root;
    while (now)
    {
        if (val(now) < val && val(now) > ans)
        {
            ans = val(now);
        }
        if(val > val(now))
        {
            now = rs(now);
        }
        else
        {
            now = ls(now);
        }
    }
    return ans;
}

6.查询后驱

和前驱基本一样，不详细解释了

int upper(int val)
{
    int ans = 2147483647;
    int now = root;
    while (now)
    {
        if (val(now) > val && val(now) < ans)
        {
            ans = val(now);
        }
        if( val < val(now) )
        {
            now = ls(now);
        }
        else
        {
            now = rs(now);
        }
    }
    return ans;
}

7.完整代码

#include <bits/stdc++.h>
using namespace std;

#define val(x) t[x].val
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
#define son(x, nxt) t[x].ch[nxt]
#define fa(x) t[x].fa
#define size(x) t[x].size
#define cnt(x) t[x].cnt

#define maxn 100005
struct splayTree
{
  int val, ch[2], fa, size, cnt;
} t[maxn];
int root, tot; //root是根节点的位置；tot是节点的数量，也是当前最后一个被插入的节点的编号

void read(int &x) { scanf("%d", &x); }
void write(int x) { printf("%d\n", x); }

void pushup(int x) //更新父节点的size值
{
  size(x) = size(ls(x)) + size(rs(x)) + cnt(x);
}

int ff(int x) //查询x是它父亲的哪一个节点
{
  return rs(fa(x)) == x;
}

void connect(int x, int y, int nxt) //把x插入到y的nxt节点上
{
  son(y, nxt) = x;
  fa(x) = y;
}

void rotate(int x) //将x旋转到它父亲的位置
{
  int y = fa(x), z = fa(y);
  int fx = ff(x), fy = ff(y);

  connect(son(x, fx ^ 1), y, fx);
  connect(y, x, fx ^ 1);
  connect(x, z, fy);

  pushup(y), pushup(x);
}

void splay(int x, int y) //将x旋转到y的位置
{
  y = fa(y);
  while (fa(x) != y)
  {
      if (fa(fa(x)) == y)
          rotate(x);
      else if (ff(x) == ff(fa(x)))
          rotate(fa(x)), rotate(x);
      else
          rotate(x), rotate(x);
  }
  if (y == 0)
  {
      root = x;
      connect(x,0,1);
  }
}

void nowPoint(int val, int fa, int nxt) //新建一个节点
{
  tot++;
  fa(tot) = fa, size(tot) = cnt(tot) = 1, val(tot) = val;
  son(fa, nxt) = tot;
}

void insert(int val) //插入一个值为val的数
{
  if (root == 0)
  {
      nowPoint(val, 0, 1);
      root = tot;
      return;
  }

  int now = root;
  while (1)
  {
      size(now)++;
      if (val(now) == val)
      {
          cnt(now)++, size(now)++;
          splay(now,root);
          return;
      }
      int nxt = val(now) < val, son = son(now, nxt);
      if (!son)
      {
          nowPoint(val, now, nxt);
          splay(tot, root);
          return;
      }
      now = son;
  }
}

int find(int val)
{
  int now = root;
  while (1)
  {
      if (!now)
          return 0;
      if (val(now) == val)
      {
          splay(now, root);
          return now;
      }
      int nxt = val(now) < val, son = son(now, nxt);
      now = son;
  }
}

void delet(int val)
{
  int now = find(val);
  if (!now) return;
  if (cnt(now) > 1)
  {
      cnt(now)--, size(now)--;
      return;
  }
  if (!ls(now) && !rs(now))
  {
      root = 0;
  }
  else if (!ls(now))
  {
      root = rs(root);
      fa(root) = 0;
  }
  else if (!rs(now))
  {
      root = ls(root);
      fa(root) = 0;
  }
  else
  {
      int pos = ls(now);
      while (rs(pos))pos = rs(pos);

      splay(pos, root);
      connect(rs(now), pos, 1);
      pushup(pos);
  }
}

int Rank(int val)
{
  int now = root, s = 0;
  while ( now )
  {
      if (val(now) == val)
      {
          splay(now,root);
          return size(ls(now)) + 1;
      }
      if (val(now) < val)
      {
          s += size(ls(now)) + cnt(now);
          now = rs(now);
      }
      else
      {
          now = ls(now);
      }
  }
  return s + 1;
}

int aRank(int k)
{
  int now = root;
  while ( 1 )
  {
      int used = size(now) - size(rs(now));
      if (k > size(ls(now)) && k <= used)
      {
          break;
      }
      if (k >= used)
      {
          k -= used;
          now = rs(now);
      }
      else
      {
          now = ls(now);
      }
  }
  splay(now, root);
  return val(now);
}

int lower(int val)
{
  int ans = -2147483647;
  int now = root;
  while (now)
  {
      if (val(now) < val && val(now) > ans)
      {
          ans = val(now);
      }
      if(val > val(now))
      {
          now = rs(now);
      }
      else
      {
          now = ls(now);
      }
  }
  return ans;
}

int upper(int val)
{
  int ans = 2147483647;
  int now = root;
  while (now)
  {
      if (val(now) > val && val(now) < ans)
      {
          ans = val(now);
      }
      if( val < val(now) )
      {
          now = ls(now);
      }
      else
      {
          now = rs(now);
      }
  }
  return ans;
}

int main()
{
  int T;
  read(T);
  int k = 0;
  for(int i = 1;i<=T;i++)
  {
      int opt, val;
      read(opt);
      read(val);
      int ans;
      switch (opt)
      {
          case 1:
              insert(val);
              break;
          case 2:
              delet(val);
              break;
          case 3:
              ans = (Rank(val));
              break;
          case 4:
              ans = (aRank(val));
              break;
          case 5:
              ans = (lower(val));
              break;
          case 6:
              ans = (upper(val));
              break;
          }
          if(opt>2)
          {
              write(ans);
          }
          
  }
  return 0;
}

结语

下次奥赛课尽量更新

最后,C呆老婆镇楼