问题标题: 平衡树 & Treap

///////////////////////////////////////////////////////////////////////////////

我鸽王不鸽啦~点进来

///////////////////////////////////////////////////////////////////////////////

平衡树 & Treap

Ⅰ- 二叉查找树

特征：

1：每个节点都有权值

2：左子树上的点小于根的权值，右子树上的点大于根的权值

3：左右子树都是二叉查找树

作用：维护有序的数列，进行插入查找..................

1.遍历：

进行中序遍历就可以从小到大输出：

void print(int p){//遍历查找树 
    if(!p)return ;//边界
    print(l[p]);//左
    cout<<a[p];//中
    print(r[p]);//右 
}

2.查找：

因为已有顺序，左小右大，所以如代码：

int find(int x,int p){//查找x,p是下标 
    if(!p)return 0;//边界
    if(x==a[p])return p;//找到了
    if(x<a[p])return find(x,l[p]);//要找的比当前小，在左子树 
    if(x>a[p])return find(x,r[p]);//要找的比当前大，在右子树 
}

3.最值：

遍历左子节点，直到该节点的左子节点为空，则该节点为min

遍历右子节点，直到该节点的右子节点为空，则该节点为max

int findmin(int p){//最左边的是min 
    if(!p)return 0;//边界 
    if(!l[p])return p;//找到了 
    else return findmin(l[p]);//继续 
}
int findmax(int p){//最右边的是max 
    if(!p)return 0;//边界 
    if(!r[p])return p;//找到了 
    else return findmax(r[p]);//继续 
}

4.插入

int newnode(int x){
    a[++cnt]=x;
    return cnt;
} 
void insert(int x,int &p){//插入新的节点p，a[p]=x 
    //&p:直接引用，p改变后p的父节点的l和r都会变 
    if(!p)p=newnode(x);//新建一个以x为值的节点
    else if(x<a[p])insert(x,l[p]);
    else if(x>a[p])insert(x,r[p]); 
}

Ⅱ - Treap

平衡树treap的节点的权值满足二叉查找树

新增变量优先级pri满足根的优先级小于子节点的优先级

struct node{//treap专属结构体 
    int lc,rc;//左右子节点
    int key;//权值，左子树上的点小于根的权值，右子树上的点大于根的权值 
    int pri;//优先级，根的优先级小于子节点的优先级 
    int cnt;//可能会有重复的，记录重复的个数
    int siz;//以该节点为根的子树的大小 
}t[100010];

1.左右旋转

左旋:把根节点的右子节点作为新的根，自己作为新的左子节点

右旋:把根节点的左子节点作为新的根，自己作为新的右子节点

左右旋不改变key之间的关系，但会改变pri的关系

void upt(int &k){t[k].siz=t[t[k].lc].siz+t[t[k].rc].siz+t[k].cnt;}//更新k的size 
void zig(int &k){//左旋 
    int y=t[k].lc;//选取左节点 
    t[k].lc=t[y].rc,t[y].rc=k;//交换
    t[y].siz=t[k].siz;//新根的size
    upt(k);//更新k的size
    k=y;//新的根 
} 
void zag(int &k){//右旋 
    int y=t[k].rc;
    t[k].rc=t[y].lc,t[y].lc=k;
    t[y].siz=t[k].siz;
    upt(k);
    k=y;
}

2.插入

操作如下：

1：从根节点向左右找该节点应该插在哪里符合key的要求
2：如果当前是空节点，就新建一个节点，然后随机生成一个优先级
3：因为优先级是随机的，会破环key的关系，随意在回溯的时候要一路旋转直到都满足关系
4：如果插入后左子节点的优先级小于当前优先级，右旋
5：如果插入后右子节点的优先级小于当前优先级，左旋

void insert(int &k,int &key){//插入 
    if(!k){//如果不存在这个节点 
        k=++sum;//新的节点 
        t[k].key=key;//赋值 
        t[k].pri=rand();//随机生成优先级 
        t[k].cnt=t[k].siz=1;
        t[k].lc=t[k].rc=0; 
    }
    else ++t[k].siz;//在该节点下面新建了一个节点，size++ 
    if(t[k].key=key)++t[k].cnt;//重复元素 
    else if(key<t[k].key){ 
        insert(t[k].lc,key);//向左找 
        if(t[t[k].lc].pri<t[k].pri)zig(k);//维护pri 
    } 
    else{
        insert(t[k].rc,key);//向右找 
        if(t[t[k].rc].pri<t[k].pri)zag(k);//维护pri 
    } 
} 

3.删除

操作如下：

1-叶子节点：直接删除
2-重复元素：cnt--
3-链结点：有一个非空子节点，用该子节点代替这个节点
4-有两个非空子节点：
    1:左子节点的优先级更小：右旋，然后访问右子树，直到生成123
    2:右子节点的优先级更小：左旋，然后访问左子树，直到生成123

void cut(int &k,int &key){//删除节点 
    if(t[k].key==key){//找到了 
        if(t[k].cnt>1)t[k].cnt--,t[k].siz--;//重复元素 
        else if(!t[k].lc||!t[k].rc)k=t[k].lc+t[k].rc;//链结点
        else if(t[t[k].lc].pri<t[t[k].rc].pri)zig(k),cut(k,key);
        else zag(k),cut(k,key);
        return ;
    }//没找到 
    t[k].siz--;//维护size
    if(key<t[k].key)cut(t[k].lc,key);//向左找 
    else cut(t[k].rc,key);//向右找 
    return ; 
}