红黑树的一种变体—

简介

Arne Andersson(也是AA树名字由来)在1993年发明了这种数据结构(原paper在这儿,内含Pascal实现),简化了$\color{red}{\text{红}}\color{black}{\text{黑}}$树繁琐的调整,同时效率也有保证

颜色限制

每个点要么是红色要么是黑色
根节点为黑色
如果一个节点是红色,那么它的子节点一定是黑色
对于任意节点,从其到叶节点的任意路径上黑色节点的数量一定
左孩子一定是黑色(唯一的新约束)

级(level)

相对于红黑染色这样繁琐的概念,AA树引入了级(level)的概念来简化问题,其定义为:从当前节点到叶节点所经过的左树边条数(叶节点记为1,考虑nil节点) level 其中我们称同一级中横向连结的右树边为水平边(horizontal link)

关于级的限制

叶节点的级为1
左节点的级严格小于其父节点
右节点的级小于等于其父节点
右孙节点的级严格小于其祖父节点
每个级大于1的节点一定有两个孩子

插入

我们考虑插入一个节点后如何调整,而事实上只有两种情况需要被考虑

左水平边——倾斜(skew)操作

也就是有一个节点的左儿子和其级相等,这种情况违反了上述第二条规则 skew 我们只要把7号节点进行一次右旋操作即可,但可能形成第二种不合法的情况

两个连续的右水平边——摊平(split)操作

也就是一个节点和其右儿子、右儿子的右儿子级相等,这种情况下违法了上述第四条规则 split 此时我们也只要对15号节点执行一次左旋操作即可

删除

原论文中使用了两个全局指针来完成删除节点的操作,而我们还是考虑一下在BST的删除操作后如何调整,注意这里的调整显然是递归的

BST的删除

我们回忆一下BST的删除如何实现:

如果将删除一个叶节点,直接删除即可
如果删除一个仅有一个儿子的节点,用其儿子替代即可(AA树中,这两个的级一定为一,且一定为右儿子)
如何将删除一个有两个儿子的节点,用它的前驱或后继节点替代即可

调整

如果该节点的两个子节点的级与其自身相差大于一时需要降低该节点的级。当一个节点是其父节点右水平边所至的,且其父节点降级,那么该节点也需降级

接下来就是三次倾斜(对该节点、该节点的右节点和该节点右节点的右节点)和两次摊平(对该节点和该节点的右节点)操作,使降级节点的子节点仍然满足对级的约束

实现(普通平衡树)

//Author:rabbyte
#include <cstdio>
#include <cctype>
template <typename tn>void fead(tn &n) {
    tn f = 1, t = 0, r = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) t = t * 10 + ch - '0', ch = getchar();
    if (ch == '.') {ch = getchar(); while (isdigit(ch)) r *= 10, t += (ch - '0') / r, ch = getchar();}
    n = f * t;
}

struct tree_node{
    tree_node *lc, *rc;
    int level;
    int key, cnt, sz;
    tree_node(int x) {
        this->key = x;
        this->cnt = 1;
        this->sz = 1;
        this->lc = nullptr;
        this->rc = nullptr;
    }
};
tree_node *rt = nullptr;

void update(tree_node * u) {
    u->sz = u->cnt; 
    if (u->lc != nullptr) u->sz += u->lc->sz;
    if (u->rc != nullptr) u->sz += u->rc->sz;
}

tree_node * skew(tree_node * u) {
    if (u->lc != nullptr && u->lc->level == u->level) { // 右旋
        tree_node *tmp = u;
        u = u->lc;
        tmp->lc = u->rc;
        u->rc = tmp;
        update(tmp); update(u);
    }
    return u;
}

tree_node * spilt(tree_node * u) {
    if (u->rc != nullptr && u->rc->rc != nullptr && u->rc->rc->level == u->level) { // 左旋
        tree_node *tmp = u;
        u = u->rc;
        tmp->rc = u->lc;
        u->lc = tmp;
        u->level++;
        update(tmp); update(u);
    }
    return u;
}

tree_node * ins(tree_node * u, int x) {
    if (u == nullptr) u = new tree_node(x);
    else {
        if (x < u->key) u->lc = ins(u->lc, x);
        if (x == u->key) {u->cnt++; u->sz++;}
        if (x > u->key) u->rc = ins(u->rc, x);
        update(u);
    }
    u = skew(u);
    u = spilt(u);
    return u;
}

tree_node * succ(tree_node * u) {
    u = u->rc;
    while (u->lc != nullptr) u = u->lc;
    return u;
}

tree_node * pred(tree_node * u) {
    u = u->lc;
    while (u->rc != nullptr) u = u->rc;
    return u;
}

tree_node * del(tree_node * u, int x, bool is_all = false) { // 是否全部删除
    if (u == nullptr) return u;
    if (x < u->key) u->lc = del(u->lc, x, is_all);
    if (x > u->key) u->rc = del(u->rc, x, is_all);
    if (x == u->key) {
        u->cnt--; u->sz--;
        if (u->cnt == 0 || is_all) {
            if (u->lc == nullptr && u->rc == nullptr) {
                delete u;
                return nullptr;
            }
            if (u->lc == nullptr) {
                tree_node * tmp = succ(u);
                u->key = tmp->key;
                u->cnt = tmp->cnt;
                u->rc = del(u->rc, tmp->key, true);
            }
            else {
                tree_node * tmp = pred(u);
                u->key = tmp->key;
                u->cnt = tmp->cnt;
                u->lc = del(u->lc, tmp->key, true);
            }
        }
    }
    update(u);
    if ((u->lc != nullptr && u->lc->level < u->level - 1) || (u->rc != nullptr && u->rc->level < u->level - 1)) {
        if (u->rc != nullptr && u->rc->level > --(u->level)) u->rc->level = u->level;
         u = skew(u);
         if (u->rc != nullptr) {
             u->rc = skew(u->rc);
            if (u->rc->rc != nullptr) u->rc->rc = skew(u->rc->rc);
         }
         u = spilt(u);
         if (u->rc != nullptr)u->rc = spilt(u->rc);
    }
    return u;
}

tree_node * find_by_key(int x) {
    tree_node * u = rt;
    while (u != nullptr && u->key != x) {
        if (u->key > x) u = u->lc;
        else if (u->key < x) u = u->rc;
    }
    return u;
}

tree_node * find_by_kth(int x) {
    tree_node * u = rt;
    while (u != nullptr) {
        if (u->lc != nullptr && x <= u->lc->sz) u = u->lc;
        else {
            if (x > (u->lc == nullptr ? 0 : u->lc->sz) + u->cnt) {x -= (u->lc == nullptr ? 0 : u->lc->sz) + u->cnt; u = u->rc;}
            else break;
        }
    }
    return u;
}

int get_kth(int x) {
    tree_node * u = rt;
    int res = 1;
    while (u != nullptr && u->key != x) {
        if (u->key > x) u = u->lc;
        else if (u->key < x) {res += (u->lc == nullptr ? 0 : u->lc->sz) + u->cnt; u = u->rc;}
    }
    if (u->key == x && u->lc != nullptr) res += u->lc->sz;
    return res;
}

int pred_by_key(int x) {
    tree_node * u = rt;
    int res = 0;
    while (u != nullptr) {
        if (u->key < x) {res = u->key; u = u->rc;}
        else u = u->lc;
    }
    return res;
}

int succ_by_key(int x) {
    tree_node * u = rt;
    int res = 0;
    while (u != nullptr) {
        if (u->key > x) {res = u->key; u = u->lc;}
        else u = u->rc;
    }
    return res;
}

void print_tree(tree_node * u) {
    if (u == nullptr) return;
    putchar('(');
    print_tree(u->lc);
    printf("%d:%d", u->key, u->sz);
    print_tree(u->rc);
    putchar(')');
}

int n, x, opt;
int main() {
    // freopen("input.in", "r", stdin);
    // freopen("output.ans", "w", stdout);
    fead(n);
    while (n--) {
        fead(opt); fead(x);
        switch (opt) {
        case 1:
            rt = ins(rt, x);
            break;
        case 2:
            rt = del(rt, x);
            break;
        case 3:
            printf("%d\n", get_kth(x));
            break;
        case 4:
            printf("%d\n", find_by_kth(x)->key);
            break;
        case 5:
            printf("%d\n", pred_by_key(x));
            break;
        case 6:
            printf("%d\n", succ_by_key(x));
            break;
        }
        // print_tree(rt);
        // putchar('\n');
    }
    return 0;
}

Appendix:平衡树大评测

环境

代码生成器(使用了Luogu-dev团队的cyaron,其中random.sample可能在高版本Python中已被废弃)

from cyaron import *
import random

maxx = 300000

for i in range(1, 11):
    test_data = IO(file_prefix="balanced_tree", data_id = i)

    n = 600000
    nums = {}
    test_data.input_writeln(n)
    for j in range(n):
        opt_kind = random.random()
        if (len(nums) == 0 or opt_kind < 0.6):
            x = randint(1, maxx)
            test_data.input_writeln(1, x)
            if x in nums:
                nums[x] += 1
            else:
                nums[x] = 1
        elif opt_kind < 0.6:
            x = random.sample(nums.keys(), 1)
            test_data.input_writeln(2, x[0])
            nums[x[0]] -= 1
            if nums[x[0]] == 0:
                del nums[x[0]]
        elif opt_kind < 0.7:
            x = random.sample(nums.keys(), 1)
            test_data.input_writeln(3, x[0])
        elif opt_kind < 0.8:
            test_data.input_writeln(4, randint(1, len(nums)))
        elif opt_kind < 0.9:
            x = random.sample(nums.keys(), 1)
            test_data.input_writeln(5, x[0] + randint(1, 10))
        else:
            x = random.sample(nums.keys(), 1)
            test_data.input_writeln(6, x[0] - randint(1, 10))

    test_data.output_gen("balanced_tree.exe")

编译参数:-O2 -std=c++11 -lm -Wl,–stack=536870912 其中保证了输入输出方式一致

结果

benchmark

总结

非平衡树确实普遍快😂,尤其是vector太离谱了,至少在OI的数据规模下是这样的,这就是所谓写的好的暴力吧。

出人意料的是AVL树居然成为了所有平衡树中最快的,而SBT确实如论文中那样快速,WBLT却平平无奇,其他平衡树结构倒是意料之中(尤其是替罪羊,太稳了)。

所以,要想偷懒,与其顶着CE的风险使用pb_ds,还不如直接vector。而如果不需要考虑可持久化或可分裂,本文所介绍的AA树的确是综合码量(SBT实在长),思维难度(~~背诵难度~~)与效率下,比较优秀的一种平衡树。

Reference

强烈推荐,里面的可视化非常便于理解,文中大多数的图也出自这里:https://ycpcs.github.io/cs350-fall2021/lectures/AA-tree_lecture.pdf