平衡树-Treap学习笔记

最近刚学了Treap

发现这种数据结构真的是——妙啊妙啊~~

咳咳。。。。

所以发一发博客，也是为了加深蒟蒻自己的理解

顺便帮助一下各位小伙伴们

切入正题

Treap的结构体

首先，Treap有两个定义

对于权值而言，它是二叉查找树

对于优先级而言，它是堆

由此，我们将Treap保存于结构体内

struct node
{
    node* ch[2];//左右孩子指针,0为左孩子，1,为右孩子
    int v,r;//v为该节点权值;r为优先级

    node(int v):v(v){ r=rand(); ch[0]=ch[1]=NULL;}
    //构造函数，用于初始化

    int cmp(int x) const{ if(x==v) return -1; return x<v ?0:1; }
    //这里的这个成员函数将在下面解释
};
node* rt=NULL;//这个是初始的根

旋转

既然平衡树

最重要的当然是旋转啦

先上一张baidu的图

结合图理解才透彻嘛

在这张图里面

我们要将中间那个圆节点旋转到根的位置

调用函数时的参数是图中最上面那个节点

(我这样说会不会有点不明白)

//d=0代表左旋;d=1代表右旋
void rotate(node* &p,int d)//结点记得加引用
{
    node* k=p->ch[d^1];
    p->ch[d^1]=k->ch[d];
    k->ch[d]=p;
    p=k;
}

其实看着图自己模拟一下就懂了

应该不用注释了吧

插入

既然Treap是二叉查找树

那么插入自然按照二叉查找树节点的性质啦

即每个结点的左孩子权值一定小于该节点，而右孩子反之

只要按照二叉查找树的插入方式递归寻找带插入位置就好

然而

Treap还是个堆啊

所以插入后还要判断优先级

之前我们初始化优先级r为随机rand()

从而保证了整个程序平均的运行效率

void ins(node* &p,int x)//x为带插入权值，结点记得加引用
{
    if(p==NULL){ p=new node(x); return; }
    //如果结点为NULL ，则找到了带插入结点，进行初始化
    int d=p->cmp(x);
    //这里运用了结构体中的cmp函数，用以确定x该插入左孩子还是右孩子
    //若x<该结点权值，cmp返回0，插入左孩子；反之亦然
    ins(p->ch[d],x);
    //递归插入
    if( p->ch[d]->r < p->r ) rotate(p,d^1);
    //*划重点*;插入后判断优先级以保证堆的性质
}

删除

寻找待删除结点依照二叉查找树的性质

这里主要讨论找到待删除结点后的操作

void del(node* &p,int x)//结点记得加引用
{
    if(p==NULL) return;//找到空结点就返回
    if(x==p->v)//找到待删除结点
    {
        if(p->ch[0]==NULL)
        {node *k=p; p=p->ch[1]; delete(k); return;}
        else if(p->ch[1]==NULL)
        {node *k=p; p=p->ch[0]; delete(k); return;}
        //如果这个结点只有一棵子树，就以该子树代替该节点

        else//如果两棵子树都不为空
        {
            //先把优先级较高的子树旋转到根
            //然后递归再另一颗子树中删除p
            int dd=p->ch[0]->r < p->ch[1]->r ?1 :0;
            rotate(p,dd);  del(p->ch[dd],x);
            return;
        }
    }
    //递归寻找待删除结点
    int d=p->cmp(x);
    del(p->ch[d],x);
}

Treap的基本操作就这些啦

蒟蒻的OI路还是漫漫无期