不忘初心
时刻前行

  1. BST 性质
  2. 旋转 treap
  3. 非旋 treap 维护普通平衡树
  4. 非旋 treap 维护文艺平衡树

BST 性质

定义

若对于一种数据结构,其每一个节点维护集合中的一个元素的值,且每一个节点都满足被我们称为“BST 性质”的性质:

  • 任意一个节点的值大于其左左节点的值,小于右子节点的值

那么这棵树被称为满足 BST 性质的

功能

考虑问题

qwq

如果我们维护任意一种满足 BST 性质的数据结构,那么对于所有操作都可以在 O(h) 的时间复杂度内完成,其中 h 代表树高

问题

考虑最基本的插入操作,即对树的形态不做任何更改

那么 h 是不被保证的,比如在插入一个有序序列后,树高将会达到 O(n)

所以才有了接下来的各种平衡树

平衡树的本质就是通过不同方式让树高更小

treap

随机

原理

在 BST 性质的基础上,treap 还要满足堆性质

给每一个节点随机上一个索引值,treap 的堆性质指,每一个节点的索引值,都大于其子节点的索引值

那么我们在插入时,检查一下是否满足堆性质,如果不满足,我们需要调整

显然,一棵树维护相同的若干个数且均满足 BST 性质的条件下,其形态可以是不同的

则改变树的形态,或者说对换一组父子即可

维护方式

对于每一个节点,维护代表权值,随机索引值,子树大小,重复个数(即集合中有多少个数与自己所代表的权值相同)

维护子树大小如下

void maintain(int k) {
    t[k].sz = t[t[k].l].sz + t[t[k].r].sz + t[k].cnt;
}

核心操作

左旋与右旋

两者类似,知其一即可知其二

右旋,即将左儿子调整至自己的位置

记自己节点编号为 k,左儿子为 lson 其改变步骤如下:

  1. 由于在旋转后,必须找另一个节点代替 k 的左子节点(原来 lson 在这个位置),而刚好 lson 的右子节点空缺,则将 k 的左子节点改为 lson 的右子节点
  2. lson 的右子节点改为 k
  3. k 改为 lson
  4. 最后更新一下更改后的 k 与其右子节点

代码如下

void rrotate(int &k) {
    int lson = t[k].l;
    t[k].l = t[lson].r; // 自左改左右
    t[lson].r = k; // 左右改自
    k = lson; // 自改左,注意 k 是引用
    maintain(t[k].r), maintain(k);
}

左旋类似

void lrotate(int &k) {
    int rson = t[k].r;
    t[k].r = t[rson].l;
    t[rson].l = k;
    k = rson;
    maintain(t[k].r), maintain(k);
}

功能

在加入旋转操作后,treap 在插入与删除时与 BST 有区别

插入

在原 BST 插入的方式上,treap 由于要维护堆性质,所以在每次插入后都要检查一下当前节点是否满足堆性质,不满足旋转

void insert(int &k, int val) {
        if (!k) { k = newnode(val); return ; }
        if (t[k].val == val) { t[k].cnt ++, maintain(k); return ; } // 若有重复
        if (val < t[k].val) { insert(t[k].l, val); if (t[t[k].l].rnd > t[k].rnd) rrotate(k); } // 若左子节点不满足堆性质
        else { insert(t[k].r, val); if (t[t[k].r].rnd > t[k].rnd) lrotate(k); } // 若右子节点不满足堆性质
        maintain(k);
    }

删除

删除也有区别

原 BST 的删除方式是基于替换的,与求前驱后继有关,非常麻烦

而 treap 在有了旋转操作后,则变得更加简单

对于删除的节点,如果他不是叶节点,则旋转他直至他成为叶节点即可

void remove(int &k, int val) {
        if (!k) return ;
        if (t[k].val == val) {
            if (t[k].cnt > 1) { t[k].cnt --, maintain(k); return ; }
            if (t[k].l || t[k].r) {
                if (t[k].l) rrotate(k), remove(t[k].r, val);
                else lrotate(k), remove(t[k].l, val);
                maintain(k);
            } else k = 0;
            return ;
        }
        val < t[k].val ? remove(t[k].l, val) : remove(t[k].r, val);
        maintain(k);
    }

总结

treap 的旋转操作与 rand 的本质,其实是随机打乱了插入的顺序,使得原本想要使用有序数列来卡 BST 的方式不再有效

注意在旋转后也要根新节点的 sz

非旋 treap

拆合

维护方式

对于每一个节点,维护代表权值,随机索引值,子树大小

维护子树大小如下

void mt(int k) {
    t[k].sz = t[t[k].ch[0]].sz + t[t[k].ch[1]].sz + 1;
}

核心操作

拆分

让我们跳出旋转,考虑拆分与合并

如果我们将树中的所有 \leq val 的值单独提出来,在不改变其原有的层级关系下组成一棵新树,将其称为左树,剩下的 > val 的数也单独提出来,不改变其原有层级关系的情况下组成一棵新树,称为右树,于是我们得到了两个新树,这被我们称为 split(拆分)操作

例如

qwq

17 为值进行拆分后会变成

qwq

考虑递归

对于一个节点 k,(比如上图的根节点)若其值已经大于拆分值,那么根据 BST 性质可以知道他的整个右子树都是属于右树的,则他就作为在以他为根解点的拆分的右子树的根,那么接下来要递归其左节点,如果在以他的左节点为根的拆分中仍有右树,则将右树接到自己左节点上,继续递归下去

按理说拆分操作应该返回一个 pair 代表以 k 为根的拆分的左子树与右子树的根的,但是有点麻烦,直接传引用来修改会更简单

void split(int k, int val, int& x, int& y) {
        if (!k) { x = y = 0; return ; }
        if (t[k].val <= val) x = k, split(t[k].ch[1], val, t[k].ch[1], y);
        else y = k, split(t[k].ch[0], val, x, t[k].ch[0]);
        mt(k);
    }

合并

即拆分操作的逆操作

我们假设所有 x 树中的节点都比 y 要小

关键在于维护堆性质

int merge(int x, int y) {
        if (!x || !y) return x | y;
        if (t[x].rnd > t[y].rnd) { t[x].ch[1] = merge(t[x].ch[1], y), mt(x); return x; }
        else { t[y].ch[0] = merge(x, t[y].ch[0]), mt(y); return y; }
    }

功能

类似拼图

插入

插入 val,先将整个树以 val 为值拆分,在将左树与新的 val 节点合并,合并后的树与拆分出的右树仍可以合并

void insert(int val) {
    int x, y;
    split(rt, val, x, y);;
    merge(merge(x, newnode(val)), y);
}

删除

单独将 val 给拆出来即可

void remove(int val) {
    int x, y, z;
    split(rt, val, x, y);
    split(x, val - 1, x, z);
    merge(x, merge(t[z].ch[0], t[z].ch[1]), y);
}

查找前驱/后继

以前驱为例,将所有小于 val 的值拆出来,在其中找最大值即可

int pre(int val) {
    int x, y;
    split(rt, val - 1, x, y);
    int k = x;
    while (t[k].ch[1]) k = t[k].ch[1];
    merge(x, y);
    return t[k].val
}
int nxt(int val) {
    int x, y;
    split(rt, val, x, y);
    int k = y;
    while (t[k].ch[0]) k = t[k].ch[0];
    merge(x, y);
    return t[k].val;
}

查询排名

排名的定义为“比 val 小的数的个数 +1”,则将所有比 val 小的数拆出来,返回根的大小 +1 即可

int getrank(int val) {
    int x, y;
    split(rt, val - 1, x, y);
    return t[x].sz + 1;
}

查询第 k 大

同照一般的 BST

void getval(int rk) {
        int k = rt;
        while (k) {
            if (t[t[k].ch[0]].sz + 1 == rk) break;
            if (rk <= t[t[k].ch[0]].sz) k = t[k].ch[0];
            else rk -= t[t[k].ch[0]].sz + 1, k = t[k].ch[1];
        }
        return t[k].val;
    }

总结

通过拆分与合并,其实与旋转 treap 的思想类似,即在保留 BST 性质的同时改变树的形态

非旋 treap 文艺平衡树

fhq-treap 也可以解决区间翻转问题

不过这时,fhq-treap 维护的值变成了下标

思想

对于反转区间 l, r,我们将整个区间分为 [1\cdots l - 1], [l \cdots r], [r + 1 \cdots n],给中间那段打上懒标记即可,注意,l, r 均是下标

核心操作

标记下传

按定义即可

void pushdown(int k) {
    if (!t[k].tag) return ; 
    swap(t[k].ch[0], t[k].ch[1]);
    t[t[k].ch[0]].tag ^= 1, t[t[k].ch[1]].tag ^= 1;
    t[k].tag = false;
}

按 size 拆分

如果我们按 val 来拆分的话,由于区间翻转会使每个下标对应的值改变,那么维护起来会很麻烦,于是我们按 size 来拆分

即一棵树的大小等于给定值,且包含最左边的节点

注意下传标记

void split(int k, int sz, int& x, int& y) {
        if (!k) { x = y = 0; return ; }
        pushdown(k);
        if (t[t[k].ch[0]].sz < sz) x = k, split(t[k].ch[1], sz - t[t[k].ch[0]].sz - 1, t[k].ch[1], y);
        else y = k, split(t[k].ch[0], sz, x, t[k].ch[0]);
        mt(k);
    }

功能

区间反转

先分割出 [l\cdots r] 这段区间,打上标记即可

void reverse(int l, int r) {
        int x, y, z;
        split(rt, l - 1, x, y);
        split(y, r - l + 1, y, z);
        t[y].tag ^= 1;
        rt = merge(x, merge(y, z));
    }

求原序列

我们可以发现,维护下标且满足 BST 性质的任何一种数据结构,其中序遍历一定是原序列

void work(int k) {
    if (!k) return ;
    pushdown(k);
    work(t[k].ch[0]), printf("%d ", k), work(t[k].ch[1]);
}

总结

维护下标而非维护值

注意下传标记

OI-数据结构-平衡树-treap

10.8 嘉祥校内模拟赛赛后题解与总结
上一篇 «
树链剖分知识总结
» 下一篇
© 2019 - 2019 bwt's blog.
...... visits · ...... visitors