入门平衡树: Treap

2022-11-16 20:27:51

入门平衡树：\(treap\)

前言：

如有任何错误和其他问题，请联系我
- 微信/QQ同号：615863087

前置知识：

二叉树基础知识，即简单的图论知识。

初识\(BST\)：

\(BST\)是\((Binary\:\:Search\:\:Tree)\)的简写，中文名二叉搜索树。
想要了解平衡树，我们就先要了解这样一个基础的数据结构: 二叉搜索树。
所以接下来会先大篇幅讨论\(BST\)
了解了\(BST\)后，\(Treap\)也就顺理成章了。
二叉树有两类非常重要的性质：
- 1：堆性质
  - 堆性质又分为大根堆性质和小根堆性质。小根堆的根节点小于左右孩子，且这是一个递归定义。对于大根堆则是大于。\(c++\)提供的\(priorioty\_queue\)就是一个大根堆。
- 2：\(BST\)性质
  - 给定一棵二叉树，树上的每个节点都带有一个数值，成为节点的“关键吗”。对于树中任意一个节点满足\(BST\)性质，指:
    - 该节点的关键码不小于他左子树的任意节点的关键码。
    - 该节点的关键码不大于他右子树的任意节点的关键码。
举个拓展的例子，笛卡尔树既满足堆性质，又满足\(BST\)性质。
- 笛卡尔树并不常见，博主也只见过几次，也偶尔成功地用别的数据结构\(AC\)掉对应的题目，是下来后看题解才发现可以用笛卡尔树写。
- 似乎可以用单调栈替代？希望了解的奆奆可以联系我或者评论区告诉我。
- 这里给出一张笛卡尔树的图片帮助大家了解\(BST\)性质和堆性质，不多做介绍。
- (图源:*)
- 笛卡尔树中的\(index\)满足\(BST\)性质，\(value\)满足堆性质。
  - 其中\(index\)是图中蓝色框出现的顺序，\(val\)是蓝色框出现的权值。
  - 很显然这棵树满足小根堆性质，也满足\(BST\)性质。
那么我们接下来介绍的二叉搜索树就是一棵满足\(BST\)性质的二叉树，可以结合此图加深理解。

\(BST\)的相关操作：

\(BST\)的建立:

为了避免数组越界同时减少特判，我们一般在\(BST\)中插入两个额外的节点，其中两个节点的权值其中一个为\(+INF\)，另一个为\(-INF\)。
不明白为什么能够减少特判可以先往下阅读。

const int INF = 0x3f3f3f3f;

int tot, root, n;

struct Treap //入门级平衡树

{

    int l, r;  //左右子节点在数组中的下标

    int val;  //节点权值

}a[maxn];

int New(int val)

{

    a[++tot].val = val;

    return tot;

}

void Build()

{

    New(-INF), New(INF);

    root = 1; a[1].r = 2;

}

\(BST\)的检索:

为了方便，我们假设树中没有相同权值的节点。
在\(BST\)中检索关键码为\(val\)的节点。根据\(BST\)性质，我们可以：
- 当\(val\)等于当前节点的关键码
  - 说明找到了这个节点
- 当\(val\)小于当前节点的关键码
  - 若当前节点左子树为空，则说明不存在\(val\)。
  - 否则递归进入左子树。
- 当\(val\)大于当前节点的关键码
  - 若当前节点右子树为空，则说明不存在\(val\)。
  - 否则递归进入右子树

int Get(int &p, int val)

{

    if(p == 0)

    {

        p = New(val);

        return;

    }

    if(val == a[p].val) return p;

    return val < a[p].val ? Get(a[p].l, val) : Get(a[p].r, val);

}

\(BST\)的插入：

为了方便，我们假设即将插入的点的权值在树中不存在。
与检索过程类似，当发现要走向的子节点为空的时候，直接建立关键码为\(val\)的新节点为\(p\)的子节点。

void ins(int &p, int val)

{

    if(p == 0)

    {

        p = New(val);

        return;

    }

    if(val == a[p].val) return;

    if(val < a[p].val) ins(a[p].l, val);

    else ins(a[p].r, val);

}

\(BST\)求前驱/后继:

\(val\)的前驱指小于\(val\)且最大的数，\(val\)的后继指大于\(val\)且最小的数。
求后继：
- 初始化\(ans\)为具有正无穷关键码的那个节点的编号。然后在\(BST\)中检索\(val\)。在检索过程中，每经过一个节点，都检查节点的关键码，判断能否更新所求的后继。
- 检索完成有三种可能：
- \(1:\) 没有找到\(val\)，此时\(val\)的后继就在已经经过的节点中。此时\(ans\)为所求。
- \(2:\) 找到了关键码为\(val\)的节点\(p\)，但\(p\)没有右子树。那么此时的\(ans\)为所求。
- \(3:\) 找到了关键码为\(val\)的节点\(p\)，且\(p\)有右子树，那么就从\(p\)的右孩子出发一直向左走，就找到了\(val\)的后继。
```
int GetNext(int val)

{

    int ans = 2; // a[2].val = INF

    int p = root;

    while(p)

    {

        if(val == a[p].val)

        {

            if(a[p].r > 0)

            {

                p = a[p].r;

                while(a[p].l > 0) p = a[p].l;

                ans = p;

            }

            break;

        }

        if(a[p].val >val && a[p].val < a[ans].val) ans = p;

        p = val < a[p].val ? a[p].l : a[p].r;

    }

    return a[ans].val;

}
```

\(BST\)的节点删除：

从\(BST\)中删除节点权值为\(val\)的数字。
首先检索得到权值为\(val\)的节点\(p\)。
节点\(p\)的子节点数目小于\(2\)，则直接删除该节点，并让子节点代替\(p\)的位置。
若\(p\)节点又有左子树又有右子树，则求出\(p\)的后继节点\(next\)。根据我们上面的分析，后继是进入右子树后一直往左走，那么这个后继节点\(next\)是不会有左子树的。这一点可以用反证法简单的证明一下。
- 如果此时的\(next\)节点有左子树，此时再来看后继的定义：大于\(val\)的最小数，那么此时\(next\)再往左走能得到大于\(val\)的且比\(next\)节点权值更小的一个数，即\(next\)不为\(p\)的后继节点。矛盾。
此时我们直接删除节点\(next\)(删除之前要记录一下)，再用\(next\)的右子树代替节点\(next\)的位置，再删除\(p\)，再用记录下来的\(next\)代替\(p\)的位置。

其他：

来解决一下为什么插入两个特殊的节点能减少特判的原因。
在主观上，我们去画图模拟这样一棵\(BST\)，有没有这两个节点是无所谓的。但是到了代码实现里，插入这两个节点却极大的方便了我们代码的编写。
手动模拟插入几个节点试试看会是什么样：
这样的话十分清楚了，如果我们插入的时候还没有节点我们也可以直接插入，检索前驱后继也可以分别从一号或者二号节点开始，即使删除操作把点全部删光了依然会有两个节点在那。我们每次操作只需要关注我们想做的事，不需要关注什么乱七八糟的有没有节点啊，树是不是空的啊，查找前驱我应该从哪里开始啊等等等等的问题，就能完完全全根据伪代码写。(话糙理不糙)【划掉。

\(BST\)复杂度分析

\(BST\)时间复杂度分析：

一棵\(N\)个节点的二叉树深度一般为\(logN\)，所以他也能保证每一次操作的复杂度为\(O(logN)\)。
但是当遇到插入一个有序序列的情况，那么\(BST\)将退化成一条链，操作的复杂度也将退化为\(O(n)\)。
为了解决这个问题，保证\(BST\)的平衡，产生了各种平衡树如\(AVL\)树，红黑树，替罪羊树等。
- (这三个除了红黑树以外我都没了解过\(QwQ\))
其中入门级别的平衡树是\(Treap\)，较为常用的是\(Splay\)。本着入门的精神，接下来我们来看看\(Treap\)。

\(Treap\)

旋转操作：

对于一个序列\(1,2,3,4,5\)，或者乱序成\(2,3,1,5,4\)。将它们插入\(BST\)中，得到的\(BST\)其实是等价的。但是第一种显然在复杂度上不占优。
我们将通过变形来更改\(BST\)的形态但同时让他保持原来的信息这样的操作，叫做"旋转"。旋转又分为左旋和右旋。
可以结合此图加深理解
即我们可以通过旋转来将原本退化的\(BST\)通过等价变换成为一棵能保证复杂度的树。

什么样旋转是合理的？

在随机数据下，一棵\(BST\)就是平衡的。所以\(treap\)的思想就是利用随机来创造平衡条件。
\(treap\)是\(tree\)和\(heap\)的结合。所以\(treap\)有两个关键字，一个是随机附上的数值，一个是原本的权值。
当我们插入一个新结点的时候，我们对其附上一个随机值，然后像二叉堆那样进行左旋或者右旋来进行调整，这样既能保证平衡性又能保证\(BST\)性质。
- 好像有点靠脸\(AC\)的意思？【划掉
- 但只要没有被大佬\(\%\)而导致\(rp-=INF\)问题应该也不大。
- \(Splay\)是一个不错的选择，更通用，也不会因为随机建值靠脸拿分。

模板题:

Acwing255: 普通平衡树

洛谷3369: 普通平衡树

两个地址提供的是一道题，但建议两个地方都交一下。
代码模板源于蓝书，详细注释

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 10;

const int INF = 0x3f3f3f3f;

int tot, root, n;

struct Treap

{

    int l, r;  //左右子节点

    int val, dat; //Bst的权值 堆的权值 满足大根堆性质

    int cnt, sz;  //重复的数量 子树(包括根节点)的大小

}a[maxn];

//新建一个节点

int New(int val)

{

    a[++tot].val = val;

    a[tot].dat = rand(); //给堆的那一部分附上随机值

    a[tot].cnt = a[tot].sz = 1; //此时重复数和子树都为1

    return tot;

}

void update(int p){ //更新当前父节点的信息

    a[p].sz = a[a[p].l].sz + a[a[p].r].sz + a[p].cnt;

}

//初始建立treap 其中有两个特殊节点

void Build()

{

    New(-INF), New(INF);

    root = 1; a[1].r = 2;

    update(root); //更新根节点

}

int GetRankByVal(int p, int val)

{

    if(p == 0) return 0; //如果没有这个节点

    //如果此时找到了 那么排名就为小于他的数字+自身

    if(val == a[p].val) return a[a[p].l].sz + 1;

    //可以直接向左走

    if(val < a[p].val) return GetRankByVal(a[p].l, val);

    //向右走的话其实就相当于左半部分加上根全部小于他

    return GetRankByVal(a[p].r, val) + a[a[p].l].sz + a[p].cnt;

}

//查找排名为rk的数

int GetValByRank(int p, int rk)

{

    if(p == 0) return INF; //空节点

    //如果当前节点左子树的规模大于rk

    //那么说明答案一定在左子树中

    if(a[a[p].l].sz >= rk)

        return GetValByRank(a[p].l, rk);

    if(a[a[p].l].sz + a[p].cnt >= rk)

        return a[p].val;

    //向右走的时候rk要减去左子树和根节点的规模

    return GetValByRank(a[p].r, rk - a[a[p].l].sz - a[p].cnt);

}

void zig(int &p) //右旋操作

{

    int q = a[p].l;  //左子树

    a[p].l = a[q].r; //左子树的右子树拼接到根节点的左子树上

    a[q].r = p; //左子树的右子树变为根节点 左子树的左子树不变

    p = q;   //把原来左子树的信息换过去

    update(a[p].r); update(p);//例行更新两个父节点的信息

}

void zag(int &p) //左旋操作 同理与右旋

{

    int q = a[p].r;

    a[p].r = a[q].l; a[q].l = p; p = q;

    update(a[p].l); update(p);

}

//插入和删除操作 一般会涉及到旋转

//所以这时候采用递归写法 以便于更新节点信息

void ins(int &p, int val)

{

    if(p == 0)

    {

        p = New(val);

        return;

    }

    if(val == a[p].val)

    {

        a[p].cnt++; update(p);

        return;

    }

    if(val < a[p].val)

    {

        ins(a[p].l, val); //因为需要满足大根堆性质

        //当我的左子节点的堆权值大于根节点的时候

        //右旋把左子节点换上来

        if(a[p].dat < a[a[p].l].dat) zig(p);

    }

    else

    {

        ins(a[p].r, val);

        if(a[p].dat < a[a[p].r].dat) zag(p);

    }

    update(p);

}

//找到需要删除的节点并将其下旋至叶子节点后删除

//减少维护节点信息等复杂问题

void del(int &p, int val)

{

    if(p == 0) return;

    if(val == a[p].val)//检测到了val

    {

        if(a[p].cnt > 1)

        {

            a[p].cnt--, update(p); //直接减掉一个副本即可

            return; //退出

        }

        if(a[p].l || a[p].r)//不是叶子节点 向下旋转

        {

            if(a[p].r == 0 || a[a[p].l].dat > a[a[p].r].dat)

            {zig(p); del(a[p].r, val);} //右旋 后进入右子树

            else {zag(p); del(a[p].l, val);}

            update(p);//例行更新父节点信息

        }

        else p = 0;  //是叶子节点 直接删除

        return;

    }

    val < a[p].val ? del(a[p].l, val) : del(a[p].r, val);

    update(p);

}

int GetPre(int val)

{   //前驱:小于x且最大的数

    int ans = 1; //a[1].val = -INF

    int p = root;

    while(p)

    {

        if(val == a[p].val) //找到了节点值相同的

        {

            if(a[p].l > 0)  //如果有左子树

            {

                p = a[p].l; //不停向右走

                while(a[p].r > 0) p = a[p].r;

                ans = p;

            }

            break;  //此时的ans为答案

        }

        //就算找不到val 前驱也被ans经过了

        if(a[p].val < val && a[p].val > a[ans].val) ans = p;

        p = val < a[p].val ? a[p].l : a[p].r;

    }

    return a[ans].val;

}

int GetNext(int val)

{   //后继:大于x且最小的数

    int ans = 2; // a[2].val = INF

    int p = root;

    while(p)

    {

        if(val == a[p].val)

        {

            if(a[p].r > 0)

            {

                p = a[p].r;

                while(a[p].l > 0) p = a[p].l;

                ans = p;

            }

            break;

        }

        if(a[p].val >val && a[p].val < a[ans].val) ans = p;

        p = val < a[p].val ? a[p].l : a[p].r;

    }

    return a[ans].val;

}

int main()

{

    Build();

    scanf("%d", &n);

    int op, x;

    while(n--)

    {

        scanf("%d%d", &op, &x);

        if(op == 1)

        {//插入x数

            ins(root, x);

        }

        if(op == 2)

        {//删除x(若有多个x,只删除一个)

            del(root, x);

        }

        if(op == 3)

        {//查询x的排名(排名定义为比当前数小的个数+1)

         //若有多个相同的数 输出最小的排名

            printf("%d\n", GetRankByVal(root, x) - 1);

        }

        if(op == 4)

        {//查询排名为x的数

            printf("%d\n", GetValByRank(root, x + 1));

        }

        if(op == 5)

        {//求x的前驱(小于x且最大的数)

            printf("%d\n", GetPre(x));

        }

        if(op == 6)

        {//求x的后继(大于x且最小的数)

            printf("%d\n", GetNext(x));

        }

    }

    return 0;

}

码农公寓

入门平衡树：\(treap\)

前言：

前置知识：

初识\(BST\)：

\(BST\)的相关操作：

\(BST\)的建立:

\(BST\)的检索:

\(BST\)的插入：

\(BST\)求前驱/后继:

\(BST\)的节点删除：

其他：

\(BST\)复杂度分析

\(BST\)时间复杂度分析：

\(Treap\)

旋转操作：

什么样旋转是合理的？

模板题:

相关文章