c

casperwu

V1

2022/07/24阅读:10主题:橙心

Treap

1 Treap的定义

Treap(树堆) = Tree + Heap

使用BST和Heap组合而成的平衡树。

Treap的每个节点保存两个值:

  1. key,即原始值
  2. val,即额外的权值,用于堆(大根堆、小根堆都可)

Treap首先是一棵二叉搜索树,节点的关键码(key)满足BST性质: 所有左节点的值 <= 根节点的值 <= 所有右节点的值

Treap 也是一个堆(以大根堆为例),节点的额外权值(val)满足大根堆的性质:父节点 > 子节点

2 Treap 最主要的操作

2.1 左旋、右旋

右旋:将当前节点顺时针旋转变成右子节点。 左旋:将当前节点逆时针旋转变成左子节点。

左右旋转不会改变Treap的BST性质,其目的是为了交换子节点和父节点。

2.2 插入数据

根据BST的性质,需要在叶节点插入数据,插入数据后需要判断此时是否满足大根堆的性质,不满足时需要通过左旋或右旋进行调整,使其满足大根堆性质。

2.3 删除数据

根据BST的性质,先找到需要删除的节点,然后通过左旋或右旋将其变换到叶节点,然后在删除该节点即可。

3 模板题目

Treap模板题目
Treap模板题目

3.1 模板代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5, INF = 1e8;

int n;
struct Node {
    int l, r;
    int key;  // 关键字
    int val;  // 大根堆维护的值
    int cnt;  // key的值出现的次数
    int sz;   // 以当节点为根的包含的子树中的节点数, 方便求排名
} tr[N];

// root 表示树根, idx 用于记录分配的节点
int root, idx;

// 使用p节点的左右孩子节点 更新p节点的信息
void pushup(int p) {
    tr[p].sz = tr[tr[p].l].sz + tr[tr[p].r].sz + tr[p].cnt;
}

// 直接创建一个叶节点
int get_node(int key) {
    tr[++idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].sz = 1;
    return idx;
}

// 右旋, 因为会修改根节点, 因此传入引用
void zig(int &p) {
    int q = tr[p].l;
    tr[p].l = tr[q].r;
    tr[q].r = p;
    p = q; // 根节点现在变成了q
    
    pushup(tr[p].r), pushup(p);
}

// 左旋
void zag(int &p) {
    int q = tr[p].r;
    tr[p].r = tr[q].l;
    tr[q].l = p;
    p = q;
    
    pushup(tr[p].l), pushup(p);
}

// 初始化树
void build() {
    // 为了方便处理, 先建立两个节点作为哨兵
    get_node(-INF), get_node(INF);
    
    root = 1;  // 以负无穷作为整个树的根节点
    tr[1].r = 2;  // 以正无穷作为根节点的右孩子
    
    pushup(root);

    // 为了保证满足大根堆的性质
    if(tr[1].val < tr[2].val) zag(root);
}

// 插入一个节点
void insert(int &p, int key) {
    // 到达叶节点的位置了, 可以直接新建一个节点
    if(!p) p = get_node(key);
    else if(tr[p].key == key) tr[p].cnt++;  // 树中存在重复值, 将该值的个数 +1 即可
    else if(tr[p].key > key) {  // 插入的值比当前根节点的值小, 则需要插入到左子树中
        insert(tr[p].l, key);
        
        // 新插入的点的val 值 > 根节点的val, 为了满足大根堆, 需要右旋
        if(tr[tr[p].l].val > tr[p].val) zig(p);
    } else {  // 插入到右子树中
        insert(tr[p].r, key);
        // 新插入的右子树的val值 > 根节点的val, 需要左旋
        if(tr[tr[p].r].val > tr[p].val) zag(p);
    }
    pushup(p);
}

// 删除一个节点
void remove(int &p, int key) {
    if(!p) return;  // 到达了叶节点, 直接返回
    
    if(tr[p].key == key) {  // 找到了删除的值
        if(tr[p].cnt > 1) tr[p].cnt--;  // 判断该值是否有多个一样的值
        else if(tr[p].l || tr[p].r) {  // 该节点不是叶节点
            // 右子树为空或者左子树的val > 右子树val, 则右旋
            if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) {
                zig(p);
                // 此时p的层级会向叶节点靠拢, 继续递归删除
                remove(tr[p].r, key);
            } else {
                zag(p);
                remove(tr[p].l, key);
            }
        } else p = 0// p此时是叶节点, 可以直接删除, 将值设置为0就可以删掉这个节点
    } else if(tr[p].key > key) {  // 递归左子树
        remove(tr[p].l, key);
    } else {
        remove(tr[p].r, key);
    }
    pushup(p);
}

// 通过key找排名
int get_rank_by_key(int &p, int key) {
    if(!p) return 0;  // 未找到节点, 返回一个非法值即可.
    
    if(tr[p].key == key) return tr[tr[p].l].sz + 1;  // 找到了值, 其排名就是左子树的节点个数 +1
    if(tr[p].key > key)  return get_rank_by_key(tr[p].l, key);  // 根节点的key > key 需要在左子树中找
    // 在右子树中找, 排名需要加上左子树和根节点的元素个数
    return tr[tr[p].l].sz + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}

// 通过排名找数值
int get_key_by_rank(int &p, int rank) {
  if(!p) return INF;  // 未找到, 返回一个非法值即可

    // 左子树的节点个数已经 >= rank, 说明要找的值在左子树中
    if(tr[tr[p].l].sz >= rank) return get_key_by_rank(tr[p].l, rank);
    // 左子树的节点数 + 根节点的元素个数 >= rank, 说明值就是根节点
    if(tr[tr[p].l].sz + tr[p].cnt >= rank) return tr[p].key;
    // 在右子树中找, 此时排名需要减去 左子树的个数和根节点的元素个数
    else return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].sz - tr[p].cnt);
}

// 找到严格小于key的最大数
int get_prev(int p, int key) {
    // 未找到, 返回一个非法值即可
    if(!p) return -INF;

    // 由于是严格小于, 因此当根节点的key >= key 时, 需要在左子树中找
    if(tr[p].key >= key) return get_prev(tr[p].l, key);
    // 在右子树中找, 此时根节点也可能是答案
    return max(tr[p].key, get_prev(tr[p].r, key));
}

// 找到严格大于key的最小数
int get_next(int p, int key) {
    // 未找到
    if(!p) return INF;
    // 由于是严格大于, 此时根 <= key, 因此需要在右子树中找
    if(tr[p].key <= key) return get_next(tr[p].r, key);
    // 在左子树中找, 此时根节点也可能是答案
    else return min(tr[p].key, get_next(tr[p].l, key));
}

int main() {
    // 初始化树
    build();
    
    cin >> n;
    while(n--) {  // 处理输入
        int opt, x; cin >> opt >> x;
        if(opt == 1) insert(root, x);
        else if(opt == 2) remove(root, x);
        
        // -1 是因为有一个负无穷的哨兵, 因此它的排名要减一
        else if(opt == 3cout << get_rank_by_key(root, x) - 1 << endl;
        // +1 也是因为有个负无穷的哨兵
        else if(opt == 4cout << get_key_by_rank(root, x + 1) << endl;
        else if(opt == 5cout << get_prev(root, x) << endl;
        else cout << get_next(root, x) << endl;
    }
    return 0;
}

分类:

后端

标签:

后端

作者介绍

c
casperwu
V1