首页 > 其他分享 >平衡树

平衡树

时间：2023-12-11 19:55:52浏览次数：33  
标签：cnt return 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 - 【模板】普通平衡树 (treap)

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], dat[N], son[N][2], siz[N], cnt[N], tot, root;
    int New(int v) {
        val[++ tot] = v;
        dat[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 (dat[u] < dat[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] || dat[son[u][0]] > dat[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;
}

struct Treap {
	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;

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

相关文章

  • 8.平衡二叉树
    110.平衡二叉树1、概要给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例1:给定二叉树[3,9,20,null,null,15,7]和二叉树最大深度有很大区别leetcode中强调的深度和高度很......
  • 平衡树（无旋Treap，范浩强树）学习笔记
    平衡树：YYDS以下是常见的平衡树/要用平衡树实现的算法：Treap（有旋/无旋）Splay树WBLT（WeightBalancedLeafyTree，重量平衡线段树）SBT（SizeBalancedTree，陈启峰树）AVL树B树、B+树笛卡尔树红黑树、左偏红黑树、AA树替罪羊树\(\to\)K-DTree（k-DimensionTree）LT（LeafyTree，平......
  • 【JavaSE】数据结构（树：二叉查找树、平衡二叉树、AVL树、红黑树）
    树度：每个节点的子节点数量树高：树的总层数根节点：入度为0的节点二叉树每个节点最多有两个子节点二叉查找树任意节点左子树上的节点都小于当前节点，右子树上的节点都大于当前节点平衡二叉树任意节点的左右子树的高度差不超过1AVL树AVL树是一种平衡二叉树，得名于其发明者的......
  • 110. 平衡二叉树
    目录题目自顶向下自顶向下正解自底向上（优）题目给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。自顶向下首先，对当前节点进行处理，计算左孩子的高度，右孩子的高度，两者高度差若大......
  • 平衡树
    平衡树平衡树有好多种，边学边写吧~。目录序号类型1Treap2Splay3FHQTreap4红黑树5替罪羊树6LinkCutTree前置芝士二叉搜索树BST简介二叉搜索树是一种二叉树的树形数据结构，其定义如下：空树是二叉搜索树。若二叉搜索树的左子树不为空，则......
  • 多开工具对游戏平衡性与公平性的影响评估
    多开工具对游戏平衡性与公平性的影响评估摘要：随着网络游戏的普及，一些玩家开始使用多开工具来同时运行多个游戏账号。然而，这种行为引发了一系列讨论，涉及到游戏的平衡性和公平性问题。本文将评估多开工具对游戏平衡性与公平性的影响，并提出相应的观点。引言：多开工具是一种允许玩......
  • 全局平衡二叉树学习笔记 && [SDOI2017]切树游戏解题报告
    首先，任何一个卡树剖的出题人都很没有素质前言2023年8月22日，XDFnoip模拟赛场上，神犇liuhangxin自己发明了矩阵乘法维护FWT，可是出成绩的时候发现本题挂了30分。2023年9月22日，菜鸡cool_milo看到了liuhangxin的题解，但是由于太菜，并没有看懂。2023年10月22日，菜......
  • 第7章. 平衡二叉搜索树
    平衡二叉搜索树(BalancedBinarySearchTree)1.1二叉搜索树存在的问题添加、删除节点时，都可能导致二叉搜索树退化成链表。为了防止二叉搜索树退化成链表，让添加、删除搜索的复杂度维持在O(logn)，提出平衡的概念。1.2平衡(Balance)平衡：当节点数量固定时，左右子树的高度越......
  • 16_平衡二叉树
    平衡二叉树【题外话】二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。（从上往下看）二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。（从下往上看）小疑惑：为什么104.二叉树的最大深度中求的是二叉树的最大深度，也用的是后序遍历。（本质上求解的就是根节......
  • 不平衡少样本数据集的算法方案
    在图像实际的细分场景中，经常会遇到数据集不均衡以及数据集数量有限等问题，如何有效利用数据集，提升自己的算法效果，这里大刀基于自己的实际项目经验，分享在实际图像分类领域遇到问题，以及解决的方案，供参考。前言大家好，我是张大刀。之前有个智慧工地的项目，其中一个需求是监控工地......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99