leafy tree和WBLT 学习笔记

qwaszx · 2019-11-13 13:59:34 · 个人记录

我最早接触leafy应该是在18年寒假的luogu省选营，但当时太菜了什么都没听懂.

orz lxl独立想出来这玩意

因为太菜了不擅长数据结构复杂度分析，以下没有复杂度证明

Leafy Tree

leafy tree是一棵满二叉树(这里满二叉树指的是任何非叶节点都有两个儿子的二叉树)，叶子节点存储真实的信息，非叶节点的权值等于其右儿子的权值，满足二叉搜索树和堆性质，可以O(1)取单侧最值.一个例子如下:

这种结构的缺点是空间为两倍，优点是和线段树相似，可以很方便地合并信息.

以下将使用leafy来实现二叉查找树的基本功能.

节点信息

一个节点的信息包括左右儿子(ch[2])、子树内叶子节点数量(size)、权值(w).

维护子树大小不仅是为了查询，后面将会看到这个可以用来维持平衡.

struct Node
{
    int w,size,ch[2];
};
int newnode(){return poolsize?pool[poolsize--]:++node_cnt;}//pool是垃圾回收栈
int newnode(int x)//新开一个权值为x的叶子
{
    int u=newnode();
    a[u].ch[0]=a[u].ch[1]=0,a[u].w=x,a[u].size=1;
    return u;
}

合并信息(pushup)

就直接按照之前提到的，w=right.w,size=left.size+right.size

void pushup(int u)
{
    a[u].size=a[a[u].ch[0]].size+a[a[u].ch[1]].size;
    a[u].w=a[a[u].ch[1]].w;
}

对于区间问题也可以像线段树一样合并.

合并两个节点(merge)

这是leafy很特殊的一点，有了这个功能之后可以很方便地进行操作.

具体地，合并两个节点x,y就只需要新开一个节点，将其左右儿子分别设为x,y，然后pushup一下即可.

int merge(int x,int y)
{
    int u=newnode();
    a[u].ch[0]=x,a[u].ch[1]=y;
    pushup(u);return u;
}

但是注意这个功能不能滥用，需要垃圾回收.下面将会看到如果不进行垃圾回收相当于进行了可持久化.

插入(ins)

从根开始向下走，按照权值大小决定走哪个儿子.走到叶子之后建新节点并和原来的叶子合并.

void ins(int &u,int x)
{
    if(!u){u=newnode(x);return;}
    if(a[u].size==1)
    {
        u=x>a[u].w?merge(u,newnode(x)):merge(newnode(x),u);
        return;
    }
    int d=x>a[a[u].ch[0]].w;
    ins(a[u].ch[d],x),pushup(u),maintain(u);
}   

maintain函数是用来维持平衡的，下面会提到.

删除(del)

从根开始向下走，走到一个两个儿子都是叶子的节点，将这个节点设为其未被删除的叶子并回收原来的这个节点以及被删除的叶子.

注意进行垃圾回收

void del(int &u,int x)
{
    if(a[u].size==1){recycle(u),u=0;return;}
    int d=x>a[a[u].ch[0]].w;
    if(a[a[u].ch[d]].size==1)
    {
        recycle(a[u].ch[d]),recycle(u),u=a[u].ch[d^1];
        return;
    }
    del(a[u].ch[d],x),pushup(u),maintain(u);
}

维持平衡(maintain)

注意插入删除可能会导致不平衡，从而影响复杂度.需要进行一些维持平衡的操作.可以像替罪羊一样重构，也可以旋转.这里采用的是旋转.

单旋

和普通的平衡树没有什么区别.不过leafy的特殊性使得旋转可以很方便地进行.设置一个阈值\alpha，当一个儿子的size小于\alpha\cdot \text{该子树size}时进行单旋.

下面是一个单旋维持平衡的代码.复杂度不正确但是很难卡经过最新测试没有双旋跑得快

void maintain(int u)
{
    if(a[a[u].ch[0]].size<a[u].size*alpha)
    {
        a[u].ch[0]=merge(a[u].ch[0],a[a[u].ch[1]].ch[0]);
        recycle(a[u].ch[1]),a[u].ch[1]=a[a[u].ch[1]].ch[1];
        pushup(u);
        return;
    }
    if(a[a[u].ch[1]].size<a[u].size*alpha)
    {
        a[u].ch[1]=merge(a[a[u].ch[0]].ch[1],a[u].ch[1]);
        recycle(a[u].ch[0]);a[u].ch[0]=a[a[u].ch[0]].ch[0];
        pushup(u);return;
    }
}

双旋

就是转两次Z.

具体地，当Z.size>=Y.size\times \frac{1-2\alpha}{1-\alpha}时进行一次双旋，否则进行一次单旋.画一下图感受一下，这个东西确实可以使树变得更加平衡.

以下是双旋维护平衡的代码.

void rotate(int u,int d)
{
    if(d)
    {
        a[u].ch[0]=merge(a[u].ch[0],a[a[u].ch[1]].ch[0]);
        recycle(a[u].ch[1]);a[u].ch[1]=a[a[u].ch[1]].ch[1];
        pushup(u);return;
    }
    else
    {
        a[u].ch[1]=merge(a[a[u].ch[0]].ch[1],a[u].ch[1]);
        recycle(a[u].ch[0]);a[u].ch[0]=a[a[u].ch[0]].ch[0];
        pushup(u);
    }
}
void maintain(int u)
{
    int d;
    if(a[a[u].ch[0]].size<a[u].size*alpha)d=1;
    else if(a[a[u].ch[1]].size<a[u].size*alpha)d=0;
    else return;
    if(a[a[a[u].ch[d]].ch[d^1]].size>=a[a[u].ch[d]].size*aalpha)
        rotate(a[u].ch[d],d^1);
    rotate(u,d);
}

普通平衡树基本操作

包括查某个数的排名、查排名为k的数、查前驱后继.