浅谈Treap平衡树
- 先从二叉查找树谈起
- Treap平衡树的旋转操作
-
- 定义
- 建立新节点
- 右旋
先从二叉查找树谈起
二叉查找树可以用来在随机数据中高效率地查找一个数。具有以下性质：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）平均的时间复杂度为O（log n）;
（摘自360百科）
举个栗子：若将数据“ 5 , 7 , 2 , 1 , 4 5,7,2,1,4 5,7,2,1,4”插入二叉查找树中，会得到以下的图：
看上去好像很高效，但是遇到数据“ 7 , 5 , 4 , 2 , 1 7,5,4,2,1 7,5,4,2,1”，二叉查找树就没辙了：
时间复杂度一下变为了O（n）。
所以，为了保持该树的高效，我们可以对这个树进行旋转操作，但是又不改变二叉查找树的性质。今天我要介绍的就是Treap平衡树。
Treap平衡树的旋转操作
-
定义
定义自变量： t r [ ] tr[ ] tr[]结构体，其中
l l l表示该节点左儿子的编号；
r r r表示该节点右儿子的编号；
v a l val val表示该节点的实际权值（输入的权值）；
d a t dat dat表示随机赋予的权值（作用待会再讲）；
s i z e size size表示该节点的子树大小；
c n t cnt cnt表示该节点的重复个数（即输入了几个该节点的权值）
代码如下
struct treap
{
int l,r;
int val,dat;//val是实际权值,dap是随机权值
int size,cnt;//size是子树大小,cnt是元素个数
}tr[maxn];
int n;
int tot,root;
-
建立新节点
初始化：记录节点编号（tot++），更新权值 v a l val val， d a t dat dat，将子树大小和重复次数设为1。
int New(int val)
{
tot++;
tr[tot].val=val;
tr[tot].dat=rand();//赋予随机值
tr[tot].cnt=tr[tot].size=1;
return tot;
}//建立新节点
-
右旋
（To be continued）