【8】平衡树学习笔记

w9095 · 2024-07-14 17:58:02 · 算法·理论

前言

我的平衡树学得不是很好，旋转那一部分弄得不是很清楚。并且学的平衡树也没有那么多种，只有自己通用的平衡树 Splay 和小常数平衡树 Treap，刚好是两个基于旋转的平衡树。这篇学习笔记主要用于巩固平衡树知识，并为 LCT 学习笔记最好准备。

长文警告：本文一共 1757 行，请合理安排阅读时间。

UPD on 2025.8.3：添加了 FHQ-Treap，FHQ-Treap 真香！

前置知识：【6】线段树学习笔记

二叉搜索树

在本博客中，平衡树中节点 x 的左儿子记作 ch[x][0]，右儿子记作 ch[x][1]，父节点记作 fa[x]，权值记作 a[x]。

二叉搜索树是一棵二叉树，这棵二叉树的每一个节点 x 满足以下条件：

对于 y：fa[y]=x,ch[y][wh(x)]=ch[x][wh(x)\oplus1]

对于 x：fa[x]=z,ch[x][wh(x)\oplus1]=y

对于 ch[x][wh(x)\oplus1]：fa[ch[x][wh(x)\oplus1]]=y

把上述变化写成代码即可实现旋转。注意上述变化是同时发生的，旋转时需要注意不能互相影响。定义根节点父亲为 0，此时不需要特判 z 不存在，因为代入发现没有影响。

void rotate(int x)
{
    int y=f[x],z=f[y],k=wh(x);
    ch[z][wh(y)]=x;
    f[x]=z;
    ch[y][k]=ch[x][k^1];
    f[ch[x][k^1]]=y;
    ch[x][k^1]=y;
    f[y]=x;
    pushup(y);pushup(x);
}

接下来，我们可以开始讲 Treap 的核心思想了。Treap 在保证需要维护的数值满足二叉搜索树性质外，对于每一个节点额外记录一个随机赋予权值，并通过旋转使这个权值符合大根堆性质。可以证明树高都期望为 \log n 级别，因为这样做相当于随机生成一棵树，随机生成的树期望深度为 \log n，故每次操作的期望时间复杂度为 O(\log n)。

创建新节点

最简单的一部分，随机赋予权值用于保持树的平衡，其余的信息正常维护。tol[x] 表示节点 x 的元素数量，因为可能会有重复元素。

int create(int v)
{
    val[++cnt]=v;
    key[cnt]=rand();
    siz[cnt]=1;
    tol[cnt]=1;
    return cnt;
}

信息上传

类似于 【6】线段树学习笔记 中线段树的信息上传，把子节点的信息合并到父节点上。注意特判子节点不存在的情况。下面是一个维护子树大小的例子，此时不需要特判。

void pushup(int now)
{
    siz[now]=siz[ch[now][0]]+siz[ch[now][1]]+tol[now];
}

建树

为了便于应对查询时出界的情况，我们设立两个哨兵节点，一个为正无穷，一个为负无穷。显然，正无穷节点是负无穷的右子树。顺便初始化根的编号。

void build()
{
    root=create(-inf),ch[root][1]=create(inf);
    pushup(root);
}

插入

考虑从根开始遍历，通过比较与当前节点维护的信息的大小决定是往左儿子走或右儿子走。如果走到空节点，则新建一个节点维护这个插入到值。之后，在回溯的过程中判断节点的权值与其发生变化的儿子节点权值的关系，如果儿子节点权值更大，则旋转以保证大根堆性质。特别的，如果走到与当前节点维护的信息的大小相同的节点，证明有重复，直接累加即可。

void insert(int &now,int v)
{
    if(now==0)
       {
       now=create(v);
       return;
       }
    if(v==val[now])tol[now]++;
    else 
       {
        int to=0;
        if(v<val[now])to=0;
        else to=1;
        insert(ch[now][to],v);
        if(key[now]<key[ch[now][to]])rotate(now,to^1);
       }
    pushup(now);
}

删除

与插入基本一样，同样的递归方法，如果走到与当前节点维护的信息的大小相同的节点，直接将这个节点的计数减 1。如果减 1 后计数为 0，证明节点被删空，我们的策略是被这个节点旋转到叶子，避免之后对树产生影响。特别的，若走到空节点，证明被删除的元素不存在，直接返回。

在转到叶子节点的过程中，为了满足大根堆性质，我们选择权值较小的子节点交换。

void del(int &now,int v)
{
    if(now==0)return;
    if(v==val[now])
       {
       if(tol[now]>1)
          {
          tol[now]--;
          pushup(now);
          return;
          }
       else if(ch[now][0]||ch[now][1])
            {
                if(!ch[now][1]||key[ch[now][0]]>key[ch[now][1]])rotate(now,1),del(ch[now][1],v);
                else rotate(now,0),del(ch[now][0],v);
                pushup(now);
            }
       else now=0;
       return;
       }
    else 
       {
        int to=0;
        if(v<val[now])to=0;
        else to=1;
        del(ch[now][to],v);
        pushup(now);
       }
}

由排名查数值

类似于 【6】线段树学习笔记 中权值线段树的查排名，查询排名为 k 的数相当于查询第 k 小的数。考虑维护子树大小 siz[x] 与当前节点的值的出现次数 cnt[x]。