首页 > 其他分享 >平衡树

平衡树

时间：2024-02-17 20:59:54浏览次数：19  
标签：return val int siz son 平衡 节点

前置芝士——二叉搜索树 BST

简介

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

  1. 空树是二叉搜索树。
  2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
  3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
  4. 二叉搜索树的左右子树均为二叉搜索树。

操作

二叉搜索树支持 6 个基本操作：

  • 插入
  • 删除
  • 按排名查值
  • 按值查排名
  • 查前驱（小于它的最大值）
  • 查后继（大于它的最小值）

建树

没有什么复杂的操作，但是为了防止宇宙射线导致的越界，可以插入两个值为 $inf$ 和 $-inf$ 的节点。

插入

插入一个值 v，从根节点开始向下递归。

设现在所在节点为 now，分许多情况：

  1. 如果 now 为空，则在当前位置新建一个值为 v 的节点，并将 cnt 设为 1。
  2. 如果 $val_{now} == v$，那么将当前位置的 cnt 加一即可。
  3. 如果 $val_{now} > v$，递归 now 的左子树。
  4. 如果 $val_{now} < v$，递归 now 的右子树。

删除

参考插入找到要修改的节点 p

  • 如果 cnt 大于 1，则直接减一。
  • 如果 cnt 等于 1：
    • 若为叶节点，直接删除。
    • 若仅有一个儿子，删除它并让它的儿子接替位置。
    • 若有两个儿子，则让左子树中最大节点或者右子树中最小节点接替它。

按排名查值

这个操作需要预先处理出每个节点为根的子树中的 cnt 之和（下文用 siz）。

假设要查找第 k 小的数，p 为当前节点，$p_l$ 为左儿子，$p_r$ 为右儿子。

每当到达一个节点 p（从根开始）：

  • 若 $k \le siz_{p_l}$，则返回左子树中第 k 小的值。
  • 若 $siz_{p_l} < k \le siz_{p_l}+cnt_p$，则返回 p 节点的值。
  • 否则返回右子树中第 $k-siz_{p_l}-cnt_p$ 小的值。

按值查排名

类似插入时的查找方法，统计途径节点的 cnt 和其左子树的 siz 之和直至当前节点与查找值相同（不加但当前点的 cnt），对累和加一就是排名。

查前驱/后继

前驱和后继查找方法类似，以前驱为例。

尝试使用 while 循环解决，能往右子树走就往右子树走（求后继时反之），最后一个不为空的点即为前驱。

int get_pre(int v) {
    int now = root, pre;
    while (now) {
        if (v <= val[now]) now = son[now][0];
        else {
            pre = val[now];
            now = son[now][1];
        }
    }
    return pre;
}

小结

二叉搜索树非常强大，处理纯随机数据时，每次操作时间复杂度为 $O(logn)$，但是如果人为造数据的话，可能会退化成链，导致时间复杂度退化成 $O(n)$。

平衡树

平衡树有好多种，边学边写吧~。

目录

序号 类型
1 Treap
2 Splay
3 FHQ Treap
4 红黑树
5 替罪羊树
6 Link Cut Tree

概念

通过特殊的处理使 BST 不会退化成链，并使结构“平衡”（每个节点的左右子树尽量接近，以使操作复杂度可观）。通过该操作构建的 BST 就称作平衡树。

Treap

简介

Treap 就是把二叉搜索树 (Tree) 和堆 (Heap) 结合（名字亦是如此）。每个节点有两个值， 一个是该节点的值，一个是随机生成的优先级。以值为关键字，排列方式满足二叉搜索树的性质的同时，以优先级为关键字，排列方式满足堆的性质。也就是说，维护的节点将同时满足堆和二叉搜索树的性质和结构。

由于堆必定不会退化为链，因此 Treap 不会退化为链。那么可以保证操作时间复杂度维持在 $O(log n)$。

所以，每加入一个节点，就要不停旋转直到它满足满足堆的性质，以保证树的平衡。

操作

旋转 P.S. 关键操作

分为左旋和右旋，可以借图理解。

以左旋为例子，当前节点为 p，则做tmp = son[p][1],son[p][1]=son[tmp][0],son[tmp][0]=p（右旋把左右儿子部分反一下）

void Rotate(int &u, int d) { //旋转 0-左旋 1-右旋
    int tmp = son[u][d ^ 1];
    son[u][d ^ 1] = son[tmp][d];
    son[tmp][d] = u;
    PushUp(u);
    PushUp(tmp);
    u = tmp;
    return ;
}

插入

按照 BST 的插入方式插入，如果原本没有该值的节点则随机分配一个优先级。完成后再维护堆的性质，不过上移过程由单纯的 swap 变成上述旋转操作。

删除

（如果有多个，cnt 减一即可，否则）与堆一样，将节点下旋到叶子再删去。

其他

与 BST 一样。

源代码

/**********************************

Problem: luogu - P3369 - 【模板】普通平衡树

State: Accepted

From: 【模板】 

Algorithm: treap 

Author: __shadow__

Last updated on 2023.12.11

**********************************/
#include <cstdio>
#include <stdlib.h>
const int N = 1e5 + 5;
struct Treap {
    int val[N], key[N], son[N][2], siz[N], cnt[N], tot, root;
    int New(int v) {
        val[++ tot] = v;
        key[tot] = rand();
        siz[tot] = 1;
        cnt[tot] = 1;
        return tot;
    }
    void PushUp(int u) {
        siz[u] = siz[son[u][0]] + siz[son[u][1]] + cnt[u];
    }
    void Rotate(int &u, int d) { //旋转 0-左旋 1-右旋
        int tmp = son[u][d ^ 1];
        son[u][d ^ 1] = son[tmp][d];
        son[tmp][d] = u;
        PushUp(u);
        PushUp(tmp);
        u = tmp;
        return ;
    }
    void insert(int &u, int v) {
        if (!u) {
            u = New(v);
            return ;
        }
        if (v == val[u]) {
            ++ cnt[u];
            PushUp(u);
            return ;
        }
        int d = v > val[u];
        insert(son[u][d], v);
        if (key[u] < key[son[u][d]]) Rotate(u, d ^ 1);
        PushUp(u);
        return ;
    }
    void Remove(int &u, int v) {
        if (!u) return ;
        if (v == val[u]) {
            if (cnt[u] > 1) {
                -- cnt[u];
                PushUp(u);
                return ;
            }
            if (son[u][0] || son[u][1]) {
                if (!son[u][1] || key[son[u][0]] > key[son[u][1]]) {
                    Rotate(u, 1);
                    Remove(son[u][1], v);
                }
                else {
                    Rotate (u, 0);
                    Remove(son[u][0], v);
                }
                PushUp(u);
                return ;
            }
            else u = 0;
            return ;
        }
        Remove(son[u][(v > val[u])], v);
        PushUp(u);
        return ;
    }
    int get_rk(int u, int v) {
        if (!u) return 1;
        if (v == val[u]) return siz[son[u][0]] + 1;
        if (v < val[u]) return get_rk(son[u][0], v);
        return get_rk(son[u][1], v) + siz[son[u][0]] + cnt[u];
    }
    int get_val(int u, int rk) {
        if (!u) return 0;
        if (rk <= siz[son[u][0]]) return get_val(son[u][0], rk);
        if (rk <= siz[son[u][0]] + cnt[u]) return val[u];
        return get_val(son[u][1], rk - siz[son[u][0]] - cnt[u]);
    }
    int get_pre(int v) {
        int now = root, pre;
        while (now) {
            if (v <= val[now]) now = son[now][0];
            else {
                pre = val[now];
                now = son[now][1];
            }
        }
        return pre;
    }
    int get_nxt(int v) {
        int now = root, nxt;
        while (now) {
            if (v >= val[now]) now = son[now][1];
            else {
                nxt = val[now];
                now = son[now][0];
            }
        }
        return nxt;
    }
}tre;
int n;
int main() {
    scanf ("%d", &n);
    while (n --) {
        int opt, x;
        scanf ("%d%d", &opt, &x);
        if (opt == 1) tre.insert(tre.root, x);
        else if (opt == 2) tre.Remove(tre.root, x);
        else if (opt == 3) printf ("%d\n", tre.get_rk(tre.root, x));
        else if (opt == 4) printf ("%d\n", tre.get_val(tre.root, x));
        else if (opt == 5) printf ("%d\n", tre.get_pre(x));
        else if (opt == 6) printf ("%d\n", tre.get_nxt(x));
    }
    return 0;
}

FHQ Treap

简介

FHQ Treap 是基于 Treap 发明的“无旋 Treap”，代码短，易理解还速度快。

操作

FHQ Treap 的核心操作是 分裂 和 合并。就是将一棵二叉查找树按要求分成两棵或把两棵合成一棵。

分裂

常用的是按 val 或者 siz 来分裂。按 val 分裂时，分成小于等于 val 的和大于 val 的两棵树。按 siz 分列时，前 siz 个节点一棵树，剩下的另一棵。

以按 val 的为例子。用四个参数 u、v、x、y，分别表示当前节点，标准 v，分裂出的两个树当前待插入的位置。

到一个节点，有两种情况：

  1. 若 $val_u \le v$，将 u 接在树 x 下，继续分裂 u 的右子树。
  2. 若 $val_u > v$，将 u 接在树 y 下，继续分裂 u 的左子树。

Code：

void Split(int u, int v, int &x, int &y) {
    if (!u) {
        x = y = 0;
        return ;
    }
    if (val[u] <= v) {
        x = u;
        Split(son[u][1], v, son[u][1], y);
    }
    else {
        y = u;
        Split(son[u][0], v, x, son[u][0]);
    }
    PushUp(u);
    return ;
}

合并

将树 x 和 y 合并并返回根节点编号。与 Treap 相同，为防止退化成链，每个节点加入随机优先级 key，要求 key 满足大根堆。

Code：

int Merge(int x, int y) {
    if (!x || !y) return x | y;
    if (key[x] < key[y]) {
        son[y][0] = Merge(x, son[y][0]);
        PushUp(y);
        return y;
    }
    else {
        son[x][1] = Merge(son[x][1], y);
        PushUp(x);
        return x;
    }
    return 0;
}

查询第 k 大

与 Treap 一样，这次用 while 写。

Code：

int get_val(int k) {
    int p = root;
    while (1) {
        if (k <= siz[son[p][0]]) p = son[p][0];
        else {
            k -= siz[son[p][0]] + 1;
            if (!k) return val[p];
            p = son[p][1];
        }
    }
}

其他

其他操作均可使用上述三种操作实现，具体实现见代码。

例题

P3369 【模板】普通平衡树

/**********************************

Problem: luogu - P3369 - 【模板】普通平衡树

State: Accepted

From: 【模板】 

Algorithm: FHQ treap 

Author: __shadow__

Last updated on 2023.12.11

**********************************/
#include <cstdio>
#include <stdlib.h>
const int N = 1e5 + 5;
struct FHQ {
    int root, val[N], key[N], siz[N], son[N][2], tot;
    int New(int v) {
        val[++tot] = v;
        key[tot] = rand();
        siz[tot] = 1;
        return tot;
    }
    void PushUp(int u) {
        siz[u] = siz[son[u][0]] + siz[son[u][1]] + 1;
        return ;
    }
    void Split(int u, int v, int &x, int &y) {
        if (!u) {
            x = y = 0;
            return ;
        }
        if (val[u] <= v) {
            x = u;
            Split(son[u][1], v, son[u][1], y);
        }
        else {
            y = u;
            Split(son[u][0], v, x, son[u][0]);
        }
        PushUp(u);
        return ;
    }
    int Merge(int x, int y) {
        if (!x || !y) return x | y;
        if (key[x] < key[y]) {
            son[y][0] = Merge(x, son[y][0]);
            PushUp(y);
            return y;
        }
        else {
            son[x][1] = Merge(son[x][1], y);
            PushUp(x);
            return x;
        }
        return 0;
    }
    void insert(int k) {
        int tn = New(k);
        if (!root) {
            root = tn;
            return ;
        }
        int x, y;
        Split(root, k, x, y);
        root = Merge(Merge(x, tn), y);
        return ;
    }
    void remove(int k) {
        int x, y, z;
        Split(root, k, x, z);
        Split(x, k - 1, x, y);
        root = Merge(Merge(x, Merge(son[y][0], son[y][1])), z);
        return ;
    }
    int get_rk(int k) {   //rnk(int k)
        int x, y;
        Split (root, k - 1, x, y);
        int ans = siz[x] + 1;
        Merge(x, y);
        return ans;
    }
    int get_val(int k) { //kth(int k)
        int p = root;
        while (1) {
            if (k <= siz[son[p][0]]) p = son[p][0];
            else {
                k -= siz[son[p][0]] + 1;
                if (!k) return val[p];
                p = son[p][1];
            }
        }
    }
    int get_pre(int k) {   //pre
        return get_val(get_rk(k) - 1);
    }
    int get_nxt(int k) {   //nxt
        return get_val(get_rk(k + 1));
    }
} tre;
int n;
int main() {
    scanf ("%d", &n);
    while (n --) {
        int opt, x;
        scanf ("%d%d", &opt, &x);
        if (opt == 1) tre.insert(x);
        else if (opt == 2) tre.remove(x);
        else if (opt == 3) printf ("%d\n", tre.get_rk(x));
        else if (opt == 4) printf ("%d\n", tre.get_val(x));
        else if (opt == 5) printf ("%d\n", tre.get_pre(x));
        else if (opt == 6) printf ("%d\n", tre.get_nxt(x));
    }
    return 0;
}

P3391 【模板】文艺平衡树

将序列看作树的中序遍历，那么就可以发现每次区间翻转只需要将该区间的这棵树上每个非叶子节点的左右儿子互换即可。

只需要以子树大小为关键字分裂就好了。同时应用懒标记优化，就得到正解。

P.S. 一个节点被标记时其左右儿子已完成交换。

/**********************************

Problem: luogu - P3391 【模板】文艺平衡树

State: Accepted

From: 【模板】 

Algorithm: FHQ treap 

Author: __shadow__

Last updated on 2023.12.20

**********************************/
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
const int N = 1e5 + 5;
int n, m;
struct FHQ {
    int rt, val[N], key[N], siz[N], son[N][2], tot;
    long long sum[N];
    bool rev[N];
    int New(int v) {
        val[++ tot] = v;
        key[tot] = rand();
        siz[tot] = 1;
        sum[tot] = v;
        return tot;
    }
    inline void insert(const int &v) {
        int tn = New(v);
        if (!rt) {
            rt = tn;
            return ;
        }
        rt = merge(rt, tn);
        return ;
    }
    inline void PushUp(const int &u) {
        sum[u] = sum[son[u][0]] + sum[son[u][1]] + val[u];
        siz[u] = siz[son[u][0]] + siz[son[u][1]] + 1;
    }
    inline void PushRev(const int &u) {
        if (u == 0) return ;
        std :: swap(son[u][0], son[u][1]);
        rev[u] ^= 1;
        return ;
    }
    inline void PushDown(const int &u) {
        if (!rev[u]) return ;
        PushRev(son[u][0]);
        PushRev(son[u][1]);
        rev[u] = false;
        return ;
    }
    void split(int u, int k, int &x, int &y) {
        if (!u) {
            x = y = 0;
            return ;
        }
        PushDown(u);
        if (k > siz[son[u][0]]) {
            x = u;
            split(son[u][1], k - siz[son[u][0]] - 1, son[u][1], y);
        }
        else {
            y = u;
            split(son[u][0], k, x, son[u][0]);
        }
        PushUp(u);
        return ;
    }
    int merge(int x, int y) {
        if (x == 0 || y == 0) return x | y;
        PushDown(x);
        PushDown(y);
        if (key[x] < key[y]) {
            son[x][1] = merge(son[x][1], y);
            PushUp(x);
            return x;
        }
        else {
            son[y][0] = merge(x, son[y][0]);
            PushUp(y);
            return y;
        }
    }
    void reversal(int l, int r) {
        int x, y, z;
        split(rt, r, x, z);
        split(x, l - 1, x, y);
        PushRev(y);
        rt = merge(merge(x, y), z);
        return ;
    }
    void print(int u) {
        PushDown(u);
        if (son[u][0]) print(son[u][0]);
        printf ("%d ", val[u]);
        if (son[u][1]) print(son[u][1]);
        return ;
    }
}tre;

int main() {
    scanf ("%d%d", &n, &m);
    for (int i = 1;i <= n; ++ i) tre.insert(i);
    while (m --) {
        int l, r;
        scanf ("%d%d", &l, &r);
        tre.reversal(l, r);
    }
    tre.print(tre.rt);
    return 0;
}
/*
struct Treap { //--Sooke
    int rt, val[N], key[N], siz[N], son[N][2];
    ll sum[N];
    bool rev[N];
    
    inline void pushUp(const int& u) {
        sum[u] = sum[son[u][0]] + sum[son[u][1]] + val[u];
        siz[u] = siz[son[u][0]] + siz[son[u][1]] + 1;
    }
    inline void pushRev(const int& u) {
        if (u == 0) { return; }
        rev[u] ^= 1; std::swap(son[u][0], son[u][1]);
    }
    inline void pushDown(const int& u) {
        if (rev[u]) {
            pushRev(son[u][0]); pushRev(son[u][1]);
            rev[u] = false;
        }
    }
    
    void split(int u, int k, int& l, int& r) {
        if (u == 0) { l = r = 0; return; }
        pushDown(u);
        if (siz[son[u][0]] < k) {
            l = u; split(son[u][1], k - siz[son[u][0]] - 1, son[u][1], r);
        } else {
            r = u; split(son[u][0], k, l, son[u][0]);
        }
        pushUp(u);
    }
    int merge(int l, int r) {
        if (l == 0 || r == 0) { return l | r; }
        pushDown(l); pushDown(r);
        if (key[l] < key[r]) {
            son[l][1] = merge(son[l][1], r); pushUp(l); return l;
        } else {
            son[r][0] = merge(l, son[r][0]); pushUp(r); return r;
        }
    }
} tr;
*/

标签：return,val,int,siz,son,平衡,节点
From： https://www.cnblogs.com/Assassins-Creed/p/18018369

相关文章

  • 代码随想录算法训练营第十七天 | 110.平衡二叉树 （优先掌握递归）| 404.左叶子之和 （优先
    257.二叉树的所有路径 已解答简单 相关标签相关企业 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。示例1：输入：root=[1,2,3,null,5]输出：["1->2->5","1->3"]示例2：输入：ro......
  • 二逼平衡树
    它是真“二逼”啊。Describe：维护一个序列，支持以下操作：查询\(x\)在区间内的排名；查询区间内排名为\(k\)的值；修改某一位置上的数值；查询\(x\)在区间内的前驱（前驱定义为小于\(x\)，且最大的数）；查询\(x\)在区间内的后继（后继定义为大于\(x\)，且最小的数）。Solution:经典......
  • 文艺平衡树
    Describe：给定一个有\(n\)个元素且没有重复元素的序列，进行\(m\)次翻转操作，输出最终序列。Solution:翻转操作类似LCT中的makeroot,稍加改造即可。splay有一个很好的性质，就是旋转过后也不改变中序遍历的顺序。所以若将左右子树交换且对子树内的节点做同样的操作，就是一次......
  • 【文化课学习笔记】【化学】选必一：水溶液中的离子反应与平衡（下）
    【化学】选必一：水溶液中的离子反应与平衡（下）盐类水解基本概念定义：盐电离出的离子与水电离出的\(\ce{H+}\)或\(\ce{OH-}\)相互作用生成弱电解质的反应。特点：可逆：水解是可逆反应，在一定条件下达到化学平衡。程度小：通常盐类水解程度很小，一般无沉淀析出、无气体放出。例......
  • 代码随想录算法训练营第十七天| 110.平衡二叉树 257. 二叉树的所有路径 404.左叶
    110.平衡二叉树 题目链接：110.平衡二叉树-力扣（LeetCode）思路：判断平衡二叉树，就是判断两个子树的高度差，继而问题转化为了如何求子树的高度——后序遍历（主要卡在了这里)。递归函数返回的是树的高度，同时用-1来表示退出递归（一开始想着用bool型作为返回值，发现函数不好设计）。同时要关......
  • 在Go中使用接口：实用性与脆弱性的平衡货币的精度
    在Go中使用接口：实用性与脆弱性的平衡原创 TimLiu 爱发白日梦的后端 2024-02-0307:00 发表于广东 听全文爱发白日梦的后端专注Go语言领域的发展，学习成为更牛逼的架构师，日常分享Go语言、架构、软件工具的使用。168篇原创内容公众号点击上方“名......
  • 平衡小车 高速运动时 紧急避障转弯继续运动的超声波传感器代码
    以下是一个使用超声波传感器实现平衡小车高速运动时紧急避障转弯继续运动的示例代码：#include<Wire.h>//定义超声波传感器引脚constinttrigPin=2;//触发引脚constintechoPin=3;//回声引脚//定义电机引脚constintmotorA1=9;constintmotorA2=10;const......
  • 平衡树
    能pbds写pbds无pbds写fhq#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+3;intrt,tot,lc[N],rc[N],val[N],rd[N],sz[N];#definelslc[p]#definersrc[p]voidUp(intp){sz[p]=sz[ls]+sz[rs]+1;}voidSpl(intp,int......
  • 通达信大盘平衡仪优化版指标公式源码
    {指标介绍：红色大盘指数安全，绿色大盘指数调整，红箭头超跌，绿箭头超涨，分析大盘不错的工具。}总家数:=INDEXADV+INDEXDEC;多:=INDEXADV;空:=INDEXDEC;差:=INDEXADV-INDEXDEC;起稳:=Ema(EMA(多,3),5);失衡:=EMA(EMA(EMA(空,4),4),2);生命:=EMA(MA(LLV(起稳,5),3),3);平衡差:=起......
  • 【文化课学习笔记】【物理】平衡力学
    【物理】平衡力学重力大小：\(G=m\mathrm{g}\)；方向：竖直向下；\(\mathrm{g}\)：不是定值，与高度和纬度有关；高度越高，\(\mathrm{g}\)越小；纬度越高，\(\mathrm{g}\)越大。重心：测量方法：悬挂法。规则图形的重心在几何中心。误区：重心不一定在物体上。注意事项：一个装满水的气球下方开......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99