平衡树-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路还是漫漫无期