平衡树-Treap

感谢：https://www.cnblogs.com/chenhuan001/p/5788272.html

Treap是平衡树中最简单的形式

平衡树就是左节点一定小于当前节点，右节点一定大于当前节点的数，这样的树按道理来讲，对于一个序列，你按照顺序向上添加数字，应该画出来的是恒定的一个

为什么会有这么多不一样的平衡树呢，Treap , Splay , SBT

因为，但但的按照值排序的平衡树最坏的情况下可能是一条链，并且我们通过左旋和右旋的一些操作，这个树我们可以依旧保持是平衡的

因为在我们解题的过程中，数字的插入顺序显得并没与那么重要

于是，我们就引入了一个新的衡量办法，使得这棵树尽可能的均衡，就是每个节点赋予一个pri值，这个值要么大的在上面，要么小的在上面，这个倒不重要

在Treap中这个值是随机生成的，这样的话尽可能的保证了这个树的均衡性，时间复杂度也就可以尽可能的接近于O(log)

下面是今天写的三道简单题：

从word上面粘贴的代码直接到CB上可能无法运行 需要再ubunte上粘贴一下，据说是在word上直接粘贴会有一些暗藏的东西编译不了

POJ 3481
1.题意：三种操作，每个人有一个优先级和一个id，现在来银行办业务，1操作就是id为x的优先级为y的来银行办业务，也就是插入，2寻找优先级最高的那个人的id，3寻找优先级最低的那个人的id

2.不允许有相同的优先级，相同的优先级有相同的数字也不可以，因为节点值中只记录了值，没有记录出现次，在询问之后就直接删除了

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int Maxn = 1000006;    ///最多的点数
struct Tree
{
    int key , num , pri , son[2];   ///key 是树上的键值 pri是随机分配的数字 为了保证树的均衡性 使得复杂度保持在log级别
    Tree() {}
    Tree(int _key , int _num , int _pri)
    {
        key = _key;
        num = _num;
        pri = _pri;
        son[0] = son[1] = 0;
    }
} T[Maxn];
int cnt , root;

void init()
{
    cnt = 1;   ///初始化 cnt=1
    root = 0;
}
void Rotate(int &x , int p)  //1 右旋  0 左旋
{
    int y = T[x].son[!p];
    T[x].son[!p] = T[y].son[p];
    T[y].son[p] = x;
    x = y;
}
void Insert(int &x , int key , int num)   ///插入一个数字  值是num  优先级是key
{
    if(x == 0)
    {
        T[x=cnt++]=Tree(key,num,rand());
/*
        显示建的树
        printf("%d...
" , x);
        for(int i=0; i<=x; i++)
        {
            printf("%d...%d.%d.%d.%d.%d.
" , i , T[i].key , T[i].pri , T[i].num , T[i].son[0] , T[i].son[1]);
        }
*/
    }
    else
    {
        int p = key<T[x].key;
        Insert(T[x].son[!p],key,num);
        if(T[x].pri<T[T[x].son[!p]].pri)
            Rotate(x,p);
    }

}
int get(int x , int p)   ///p=1 获得优先级最大的点的数字 p=0 获得优先级最小的点的数字
{
    while( T[x].son[p] )
    {
        x = T[x].son[p];
    }
    return x;
}
void del(int &x , int key)   ///删除一个键值是key的点
{
    if(T[x].key == key)
    {
        if(T[x].son[0] && T[x].son[1])
        {
            int p = T[T[x].son[0]].pri > T[T[x].son[1]].pri;
            Rotate(x ,p);
            del(T[x].son[p] , key);
        }
        else
        {
            if( !T[x].son[0] )
                x = T[x].son[1];
            else
                x = T[x].son[0];
        }
    }
    else
    {
        int p = T[x].key > key;
        del(T[x].son[!p], key);
    }
}
int main()
{
    int flag;
    init();
    while( scanf("%d" ,&flag) != EOF )
    {
        if(flag == 0) break;
        if(flag == 1)
        {
            int num , key;
            scanf("%d%d" , &num , &key);
            Insert(root , key , num);   ///每次新建点之后 root指向的依然是最终的根节点标号
        }
        else if(flag == 2)   ///获取优先级最高的那个点的值
        {
            int x = get(root , 1);
            if(x)
            {
                printf("%d
" , T[x].num);
                del(root , T[x].key);
            }
            else
            {
                printf("0
");
            }
        }
        else if(flag == 3)   ///获取优先级最低的那个点的值
        {
            int x = get(root , 0);
            if(x)
            {
                printf("%d
" , T[x].num);
                del(root , T[x].key);
            }
            else
            {
                printf("0
");
            }
        }
    }
    return 0;
}
View Code

POJ1442

题意：现在有一个序列长度为n，下面给出这个序列，接下来m个询问，第i次询问问前u[i]个数字里面第i大的是谁

  1. 第一想法就是可以主席书写一下
  2. 现在发现平衡树也可以写，主席书的实现是多棵线段树，平衡树就是一个二叉树，主席书带有修改操作，单点修改，区间修改什么的
  3. 在上一题的基础上，将询问函数改了，每个节点现在的key值就是他本身，另外需要记录一个子树节点数，接下来像主席书一样的查找第k大
  4. 时间复杂度O(logn)
  5. 不要忘记调用init函数
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;
const int Maxn = 30004;
int a[Maxn];
int u[Maxn];

struct Tree
{
    int key , Size , pri , son[2];   ///需要记录的是每个节点的子孩子的节点的个数
    Tree() {}
    Tree(int _key , int _Size , int _pri)
    {
        key = _key;
        Size = _Size;
        pri = _pri;
        son[0] = son[1] = 0;
    }
}T[Maxn];
int root , cnt;
void init()
{
    root = 0;
    cnt = 1;
}
void Rotate(int &x , int p)
{
    int y = T[x].son[!p];
    T[x].Size = T[x].Size-T[y].Size+T[T[y].son[p]].Size;
    T[x].son[!p] = T[y].son[p];
    T[y].Size = T[y].Size-T[T[y].son[p]].Size+T[x].Size;
    T[y].son[p] = x;
    x = y;
}
void Insert(int &x , int key)
{
    if(x == 0)
    {
        T[x=cnt++] = Tree(key , 1 , rand());
    }
    else
    {
        T[x].Size++;
        int p = key<T[x].key;
        Insert(T[x].son[!p] , key);
        if(T[x].pri < T[T[x].son[!p]].pri)
            Rotate(x,p);
    }
}
int fin(int &x , int p)
{
    if(p==T[T[x].son[0]].Size+1)
        return T[x].key;
    if(p>T[T[x].son[0]].Size+1)
        fin(T[x].son[1] , p-T[T[x].son[0]].Size-1);
    else
        fin(T[x].son[0] , p);
}
int main()
{
    int n , m;
    u[0] = 0;
    while( scanf("%d%d" , &n , &m) != EOF )
    {
        init();
        for(int i=0; i<n; i++)
            scanf("%d" , &a[i]);
        for(int i=1; i<=m; i++)
        {
            scanf("%d" , &u[i]);
            for(int j=u[i-1]; j<u[i]; j++)
            {
                Insert(root , a[j]);   ///键值就是本身的值
            }
            printf("%d
" , fin(root , i));    ///寻找区间第i大
        }
    }


    return 0;
}
View Code

POJ 2352

题意：有n个星星，每个星星有自己的x坐标y坐标，星星的等级等于x轴不超过它，y轴不超过它的星星的数量，问每个等级有多少个星星

做法：这个题输入是按照y轴从小到大，x轴从小到大输入的，线段树可解，Treap就是统计x大小不超过它的有多少个

  1. 不能忘记初始化函数
  2. 输出等级是0~n-1 不是1~n
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int Maxn = 15005;
int ans[Maxn];  ///询问不同等级的有多少个星星 要是询问每个点在低级等级也是一样的
struct Tree
{
    int key , Size , pri , son[2];
    Tree(){}
    Tree(int _key , int _Size , int _pri)
    {
        key = _key;
        Size = _Size;
        pri = _pri;
        son[0] = son[1] = 0;
    }
}T[Maxn];
int root , cnt;
void init()
{
    cnt = 1;
    root = 0;
    memset(ans , 0 , sizeof(ans));
}
void Rotate(int &x , int p)
{
    int y = T[x].son[!p];
    T[x].Size = T[x].Size-T[y].Size+T[T[y].son[p]].Size;
    T[x].son[!p] = T[y].son[p];
    T[y].Size = T[y].Size-T[T[y].son[p]].Size+T[x].Size;
    T[y].son[p] = x;
    x = y;
}
void Insert(int &x , int key)
{
    if(x == 0)
    {
        T[x=cnt++] = Tree(key , 1 , rand());
    }
    else
    {
        T[x].Size++;
        int p = key<T[x].key;
        Insert(T[x].son[!p] , key);
        if(T[x].pri > T[T[x].son[!p]].pri)
            Rotate(x , p);
    }
}
int fin(int &x , int p)
{
    if(x == 0)
        return 0;
    if(T[x].key <= p)
        return T[T[x].son[0]].Size+1+fin(T[x].son[1] , p);
    else
        return fin(T[x].son[0] , p);
}
int main()
{
    int n , x , y;
    while( scanf("%d" , &n) != EOF )
    {
        init();
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d" , &x , &y);   ///题目给的很友好 Y轴按照升序给出，y轴也按照升序给出
                                       ///于是对于每一个输入，只要统计x坐标比较小的有多少个就可以了
            ans[fin(root , x)]++;
            Insert(root , x);
        }
        for(int i=0; i<n; i++)
            printf("%d
" , ans[i]);
    }
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Flower-Z/p/9800714.html