平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

平衡树初阶——AVL平衡二叉查找树

一、什么是二叉树

1. 什么是树。

计算机科学里面的树本质是一个树状图。树首先是一个有向无环图,由根节点指向子结点。但是不严格的说,我们也研究无向树。所谓无向树就是将有向树的所有边看成无向边形成的树状图。树是一种递归的数据结构,所以我们研究树也是按照递归的方式去研究的。

2.什么是二叉树。

我们给出二叉树的递归定义如下:

(1)空树是一个二叉树。

(2)单个节点是一个二叉树。

(3)如果一棵树中,以它的左右子节点为根形成的子树都是二叉树,那么这棵树本身也是二叉树。

二、BST

1.什么是二叉排序树。

二叉排序树是一种二叉树,它满足树的中序遍历是有序的。

2.BSTBinary Search Tree)。

二叉查找树是一种最普通的二叉排序树,一般称作BST,也称为B-树。在这棵树中,满足在任意一个子树中,都满足左子树 < 根节点 < 右子树,即该树的中序遍历满足从小到大排序的结果。

3.如何构造一个二叉排序树?

很显然,要想构造一个BST,就必须在插入节点时,满足下面的原则:

(1)如果节点为空,则直接插入到该节点。

(2)如果节点不为空,且要插入的值小于等于当前节点的值,那么则将该节点插入到左子树当中。

(3)如果节点不为空,且要插入的值大于当前节点的值,那么则将该节点插入到右子树当中。

4.利用BST的性质对一个数组进行剃重。

由于BST有二叉排序树的性质,我们可以利用这样的性质对一个待定数组进行剃重。原理很简单,只需要在插入的时候如果已经发现了相等的节点的话,那么则不进行插入即可。也就是说,只有该树没有的节点,我们才进行相应的插入操作。

三、BST的相关操作

1.建树(createTree

BST的建立是基于一个数组进行的,本质上是把数组中的数按顺序插入的树中。可以想象,,每插入一个数,平均时间复杂度为O(logn),所以建树的平均时间复杂度为O(nlogn)

2.查找某一个值dsearchTree

如果我们需要在BST上查找一个值d,那么我们需要从根节点开始,按照下面的思路进行递归查询:

(1)如果当前节点为空,则未找到,返回NULL。

(2)如果当前节点不为空,且当前节点的值等于d,那么则找到,返回当前节点。

(3)如果当前节点不为空,且当前节点的值大于d,那么则递归在左子树中寻找。

(4)如果当前节点不为空,且当前节点的值小于d,那么则递归在右子树中寻找。

可以想象,查找操作的平均时间复杂度为O(logn)

3.删除一个值ddeleteTree

如果我们想要删除一个值d的节点,那么显然首先需要找到该节点。如果没有找到,则删除操作失败,如果找到,继续下面的操作即可:

(1)如果找到的节点的右子树为空,那么直接用该节点的左节点替换当前节点即可。

(2)如果找到的节点的右子树不为空,且右子树的左子树不为空,则递归找该右子树的左子树。

(3)如果找到的节点的右子树不为空,且右子树的左子树为空,则:

①如果找到的该节点的右节点为空,则返回当前节点,用这个节点去替换需要删除的点即可。

②如果找到的该节点的右子树不为空,则首先用该右子树替换找到的节点,在用找到的节点替换需要删除的节点即可。

显然,删除操作的平均时间复杂度为O(logn)

四、AVL平衡二叉查找树

1.什么是平衡二叉树。

平衡二叉树是一种二叉排序树,并且满足树中任意一个节点的左右子树的高度保持平衡。

2.什么是AVL

AVL是一种二叉查找树,并且满足树中任意一个节点的左右子树的高度差的绝对值小于等于1,即保持平衡系数不大于1。AVL也称B-BST(Balanced - Binary Search Tree),而AVL的名称只是与这种数据结构的作者有关。

3.引例:为什么会产生AVL

我们为什么需要研究AVL,换句话说,为什么我们要重视BST的平衡性能呢?我们看下面的一个例子。

我们用1,2,3,4,5,6,7,8,9来进行建树。我们发现,这样建树的结果如下:

平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

可以看出,这样二叉树实际上退化为了一个链表。在最坏的情况下,插入和删除的时间复杂度都退化为了O(n)

很显然,树的平衡性越好,这种退化越不明显。所以为了保持BST的高效,我们研究AVL是必要的。

4.如何保持AVL的平衡?

既然要保持左右子树高度差小于等于1,那么我们一定需要在节点里面定义一个新的属性,用来记录该节点为根的树的高度。由于建树的过程是递归的,所以树的高度的更新也是递归完成的。通过更新高度,我们就可以知道什么时候左右子树的高度差大于1了,这个时候产生了失衡。一旦某一个节点开始失衡,那么这个时候必须通过旋转操作使二叉树达到一个新的平衡。

五、AVL的相关操作

1.旋转操作(rotateAvl

如果在某一个时刻二叉树发生了失衡,我们就需要对二叉树进行相应的旋转使得二叉树重新达到平衡。这个旋转并不是随意的,我们还要保证BST的基本性质,那就是中序遍历必须有序才行。

我们总结二叉树失衡的原因,可以归纳为以下四种情况(其中圆形节点代表失衡有关的节点,方形节点代表子树)

平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

归纳后发现,对于情况(1)(2),都是由于左子树高度大于右子树高度形成的失衡。对于情况(3)(4)则是相反的情况。且情况(1)(3)互为镜像,情况(2)(4)互为镜像。所以我们只以(1)(2)种情况作为例子,(3)(4)情况的道理同出一辙。

对于情况(1),左子树高度大于右子树高度,而在左子树中,依然是左子树高度大于右子树高度。对于这样的情况,我们需要以1为根进行右转(rightRotate),右转的结果是,2变为新的根,而1则成为2的右节点,2原本的右子树则成为了1的左子树,即,如下图:

平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

对于情况(2),左子树高度大于右子树高度,而在左子树中,左子树高度小于右子树高度。对于这样的情况,我们需要首先需要以2(leftRotate)为根进行左转,左转的结果是3变为1的左子树,而2变为3的左子树,而3原本的左子树成了2的右子树。如下图所示:

平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

之后就转化为了情况(1),故只需要在以1为根进行右转即可。

通过这样的旋转操作,AVL重新达到了平衡。

这个旋转操作的时间复杂度是O(1)的。

2.高度更新操作。

由于高度更新是递归进行的,所以我们选择回溯的阶段进行高度更新。而一个节点的高度应该是左子树高度和右子树高度的最大值再加1。

高度更新在整个AVL中是必要的,不管建树过程中,还是插入操作,或者是删除操作中,我们都需要时时刻刻对高度进行更新,只有正确的更新高度,才能判断二叉树是否失衡。而一旦失衡,我们就需要进行上述的旋转操作,这些是相辅相承的。

高度更新的时间复杂度也是O(1)的。

3.插入操作(insertAvl

在插入操作中,由于插入的新节点,有可能使原本的二叉树产生了失衡,故应该进行相应的旋转操作。故,这样插入操作能稳定在平均O(logn) 的时间复杂度内。

4.删除操作(deleteAvl

再删除操作中,由于删除了节点,也有可能是原本平衡的二叉树产生失衡,故也应该进行相应的旋转操作。故,这样删除操作能稳定在O(logn) 的时间复杂度内。

六、代码实现(C/C++)

1.对于节点数据类型的处理:

  #define Elem int //这样Elem就是节点中数据的类型。 

2.节点结构体的二叉链表

 typedef struct LNode
{
Elem data; //节点数据域
int height; //节点为根的树的高度
struct LNode *left,*right; //左子树和右子树
struct LNode() //构造函数
{
height=;
left=right=NULL;
}
}LNode,*avlTree;
//这样定义LNode是节点的类型,avlTree则是节点的指针类型。

3.右旋转子操作,返回旋转之后的根节点指针

 avlTree _rightRotate(avlTree &r)
{
int lh=,rh=;
avlTree t=r->left;
r->left=t->right;
if(r->left) lh=r->left->height;
if(r->right) rh=r->right->height;
r->height=max(lh,rh)+;
t->right=r;
if(t->left==NULL) t->height=;
else t->height=max(t->left->height,r->height)+;
return t;
}

4.左旋转子操作,返回旋转之后的根节点指针

 avlTree _leftRotate(avlTree &r)
{
int lh=,rh=;
avlTree t=r->right;
r->right=t->left;
if(r->left) lh=r->left->height;
if(r->right) rh=r->right->height;
r->height=max(lh,rh)+;
t->left=r;
if(t->right==NULL) t->height=;
t->height=max(t->height,r->height)+;
return t;
}

5.旋转主算法(发生失衡,按照规则进行旋转操作)

 void rotateAvl(avlTree &root)
{
int lh=,rh=;
if(root->left) lh=root->left->height;
if(root->right) rh=root->right->height;
root->height=max(lh,rh)+;
if(abs(lh-rh)>)
{
avlTree tp;
int lp=,rp=;
if(lh>rh) tp=root->left;
else tp=root->right;
if(tp->left!=NULL) lp=tp->left->height;
if(tp->right!=NULL) rp=tp->right->height;
if(lh>rh&&lp<rp) root->left=_leftRotate(tp);
if(lh<rh&&lp>rp) root->right=_rightRotate(tp);
if(lh>rh) root=_rightRotate(root);
else root=_leftRotate(root);
}
}

6.插入操作,向二叉树r插入d。这里用sign标记表示是否进行剃重,如果signtrue则剃重,signfalse则表示可重复。

 void insertAvl(avlTree &r,Elem d,bool sign)
{
//递归出口
if(r==NULL) {
r=new LNode();
r->data=d;
r->height++;
return;
}
if(d<=r->data)
{
if(d==r->data&&sign) return;
insertAvl(r->left,d,sign);
}
else
{
insertAvl(r->right,d,sign);
}
rotateAvl(r); //检验失衡并进行旋转
}

7. 根据data数组建树。这里用sign标记表示是否进行剃重,如果signtrue则剃重,signfalse则表示可重复。

 void createAvl(avlTree &root,Elem data[],int n,bool sign)
{
int i;
root=NULL;
for(i=;i<n;i++)
{
insertAvl(root,data[i],sign);
}
}

8.查询root里面的数据d所在节点,如果查询成功,则返回该节点。若d数据不存在,则查询失败,返回NULL

 avlTree searchAvl(avlTree root,Elem d)
{
if(root!=NULL)
{
if(d==root->data) return root;
else if(d<root->data) return searchAvl(root->left,d);
else searchAvl(root->right,d);
}
return NULL;
}

9.在删除中寻找实际需要删除的点,返回实际点。

 avlTree _delete(avlTree &root)
{
avlTree ret=root;
if(root->left) ret=_delete(root->left);
else if(root->right)
{
ret=root->right;
int t=root->data;
root->data=root->right->data;
ret->data=t;
root->height=;
root->right=NULL;
return ret;
}
else
{
root=NULL;
return ret;
}
rotateAvl(root); //检验失衡并进行旋转
return ret;
}

10.删除主操作算法,删除root上的data数据所在节点

 void deleteAvl(avlTree &root,Elem data)
{
avlTree ret;
if(!root) return;
if(root->data!=data) //未找到该节点,首先寻找该节点
{
if(data<root->data) ret=root->left;
else ret=root->right;
deleteAvl(ret,data); //递归寻找
}
else //找到该节点
{
if(!root->right) //右子树为空
{
root=root->left;
}
else //右子树不为空
{
avlTree t=_delete(root->right); //寻找实际删除的节点
root->data=t->data;
free(t);
}
}
rotateAvl(root); //检验失衡并进行旋转
}

于是我又找到了一份不错的模版总结,仅供参考!

Treap树

核心是 利用随机数的二叉排序树的各种操作复杂度平均为O(lgn)

Treap模板:

 #include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define INF 0x3f3f3f3f
#define MAXN 100005 using namespace std; int cnt=,rt=; //节点编号从1开始 struct Tree
{
int key, size, pri, son[]; //保证父亲的pri大于儿子的pri
void set(int x, int y, int z)
{
key=x;
pri=y;
size=z;
son[]=son[]=;
}
}T[MAXN]; void rotate(int p, int &x)
{
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 ins(int key, int &x)
{
if(x == )
T[x = cnt++].set(key, rand(), );
else
{
T[x].size++;
int p=key < T[x].key;
ins(key, T[x].son[!p]);
if(T[x].pri < T[T[x].son[!p]].pri)
rotate(p, x);
}
} void del(int key, int &x) //删除值为key的节点
{
if(T[x].key == key)
{
if(T[x].son[] && T[x].son[])
{
int p=T[T[x].son[]].pri > T[T[x].son[]].pri;
rotate(p, x);
del(key, T[x].son[p]);
}
else
{
if(!T[x].son[])
x=T[x].son[];
else
x=T[x].son[];
}
}
else
{
T[x].size--;
int p=T[x].key > key;
del(key, T[x].son[!p]);
}
} int find(int p, int &x) //找出第p小的节点的编号
{
if(p == T[T[x].son[]].size+)
return x;
if(p > T[T[x].son[]].size+)
find(p-T[T[x].son[]].size-, T[x].son[]);
else
find(p, T[x].son[]);
} int find_NoLarger(int key, int &x) //找出值小于等于key的节点个数
{
if(x == )
return ;
if(T[x].key <= key)
return T[T[x].son[]].size++find_NoLarger(key, T[x].son[]);
else
return find_NoLarger(key, T[x].son[]);
}

相关题目:POJ 3481 1442 2352

Splay Tree(伸展树)

核心就是 过程Splay(x, y),即将x节点转移到y节点的子节点上面(其中y是x的祖先)。

利用其中双旋的优势能够保证查询复杂度均摊为O(lgn)

一开始理解有些困难,其实实际上不做深入的理解就是,双旋的过程就是一个建立相对平衡的二叉树的一个过程。

》对于二叉树,最极端的情况就是线性插入,使得整棵二叉树退化为一条链。比如你查询链的最后一个节点,之后再次查询第一个节点。

1)若只是单旋通过Splay(x, 0)将最后一个节点移动到根节点,需要O(n)复杂度,而查询第一个节点时又需要O(n)复杂度,来来往往就退化成一条链了。

2)若是双旋Splay(x, 0)将最后一个节点移动到根节点上时,移动过程中建立起了相对平衡的二叉树,需要O(n),也就是查询第一个节点时,大概是需要O(lgn)复杂度。这就降低了复杂度。可以证明,总的每个操作的均摊复杂度是O(lgn)。

具体证明可以参见 杨思雨《伸展树的基本操作与应用》

I 用于维护单调队列 :(以key为维护对象保证单调)

常用版:(支持相同值)

  Struct Tree{

 int key, size, fa, son[];

 }

 void PushUp(int x);

 void Rotate(int x, int p); //0左旋 1右旋

 void Splay(int x, int To) //将x节点插入到To的子节点中

 int find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处

 int prev() //返回比根值小的最大值 若无返回0 若有将其转移到根处

 int succ() //返回比根值大的最小值 若无返回0 若有将其转移到根处

 void Insert(int key) //插入key 并且将该节点转移到根处

 void Delete(int key) //删除值为key的节点 若有重点只删其中一个 x的前驱移动到根处

 int GetPth(int p) //获得第p小的节点 并将其转移到根处

 int GetRank(int key) //获得值<=key的节点个数 并将其转移到根处 若<key只需将<=换为<

模板:

 int cnt=, rt=;

 struct Tree
{
int key, size, fa, son[];
void set(int _key, int _size, int _fa)
{
key=_key;
size=_size;
fa=_fa;
son[]=son[]=;
}
}T[MAXN]; inline void PushUp(int x)
{
T[x].size=T[T[x].son[]].size+T[T[x].son[]].size+;
} inline void Rotate(int x, int p) //0左旋 1右旋
{
int y=T[x].fa;
T[y].son[!p]=T[x].son[p];
T[T[x].son[p]].fa=y;
T[x].fa=T[y].fa;
if(T[x].fa)
T[T[x].fa].son[T[T[x].fa].son[] == y]=x;
T[x].son[p]=y;
T[y].fa=x;
PushUp(y);
PushUp(x);
} void Splay(int x, int To) //将x节点插入到To的子节点中
{
while(T[x].fa != To)
{
if(T[T[x].fa].fa == To)
Rotate(x, T[T[x].fa].son[] == x);
else
{
int y=T[x].fa, z=T[y].fa;
int p=(T[z].son[] == y);
if(T[y].son[p] == x)
Rotate(x, !p), Rotate(x, p); //之字旋
else
Rotate(y, p), Rotate(x, p); //一字旋
}
}
if(To == ) rt=x;
} int find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处
{
int x=rt;
while(x && T[x].key != key)
x=T[x].son[key > T[x].key];
if(x) Splay(x, );
return x;
} int prev() //返回比根值小的最大值 若无返回0 若有将其转移到根处
{
int x=T[rt].son[];
if(!x) return ;
while(T[x].son[])
x=T[x].son[];
Splay(x, );
return x;
} int succ() //返回比根值大的最小值 若无返回0 若有将其转移到根处
{
int x=T[rt].son[];
if(!x) return ;
while(T[x].son[])
x=T[x].son[];
Splay(x, );
return x;
} void Insert(int key) //插入key 并且将该节点转移到根处
{
if(!rt)
T[rt = cnt++].set(key, , );
else
{
int x=rt, y=;
while(x)
{
y=x;
x=T[x].son[key > T[x].key];
}
T[x = cnt++].set(key, , y);
T[y].son[key > T[y].key]=x;
Splay(x, );
}
} void Delete(int key) //删除值为key的节点 若有重点只删其中一个 x的前驱移动到根处
{
int x=find(key);
if(!x) return;
int y=T[x].son[];
while(T[y].son[])
y=T[y].son[];
int z=T[x].son[];
while(T[z].son[])
z=T[z].son[];
if(!y && !z)
{
rt=;
return;
}
if(!y)
{
Splay(z, );
T[z].son[]=;
PushUp(z);
return;
}
if(!z)
{
Splay(y, );
T[y].son[]=;
PushUp(y);
return;
}
Splay(y, );
Splay(z, y);
T[z].son[]=;
PushUp(z);
PushUp(y);
} int GetPth(int p) //获得第p小的节点 并将其转移到根处
{
if(!rt) return ;
int x=rt, ret=;
while(x)
{
if(p == T[T[x].son[]].size+)
break;
if(p>T[T[x].son[]].size+)
{
p-=T[T[x].son[]].size+;
x=T[x].son[];
}
else
x=T[x].son[];
}
Splay(x, );
return x;
} int GetRank(int key) //获得值<=key的节点个数 并将其转移到根处 若<key只需将<=换为<
{
if(!rt) return ;
int x=rt, ret=, y;
while(x)
{
y=x;
if(T[x].key <= key)
{
ret+=T[T[x].son[]].size+;
x=T[x].son[];
}
else
x=T[x].son[];
}
Splay(y, );
return ret;
}

完全版:(支持相同值,支持区间删除,支持懒惰标记)

  Struct Tree{

 int key, num, size, fa, son[];

 }

 void PushUp(int x);

 void PushDown(int x);

 int Newnode(int key, int fa); //新建一个节点并返回

 void Rotate(int x, int p); //0左旋 1右旋

 void Splay(int x, int To); //将x节点移动到To的子节点中

 int GetPth(int p, int To); //返回第p小的节点 并移动到To的子节点中

 int Find(int key); //返回值为key的节点 若无返回0 若有将其转移到根处

 int Prev(); //返回根节点的前驱

 int Succ(); //返回根结点的后继

 void Insert(int key); //插入key值

 void Delete(int key); //删除值为key的节点

 int GetRank(int key); //获得值<=key的节点个数

 void Delete(int l, int r); //删除值在[l, r]中的节点 

模板:

 int cnt, rt;
int Add[MAXN]; struct Tree{
int key, num, size, fa, son[];
}T[MAXN]; inline void PushUp(int x)
{
T[x].size=T[T[x].son[]].size+T[T[x].son[]].size+T[x].num;
} inline void PushDown(int x)
{
if(Add[x])
{
if(T[x].son[])
{
T[T[x].son[]].key+=Add[x];
Add[T[x].son[]]+=Add[x];
}
if(T[x].son[])
{
T[T[x].son[]].key+=Add[x];
Add[T[x].son[]]+=Add[x];
}
Add[x]=;
}
} inline int Newnode(int key, int fa) //新建一个节点并返回
{
++cnt;
T[cnt].key=key;
T[cnt].num=T[cnt].size=;
T[cnt].fa=fa;
T[cnt].son[]=T[cnt].son[]=;
return cnt;
} inline void Rotate(int x, int p) //0左旋 1右旋
{
int y=T[x].fa;
PushDown(y);
PushDown(x);
T[y].son[!p]=T[x].son[p];
T[T[x].son[p]].fa=y;
T[x].fa=T[y].fa;
if(T[x].fa)
T[T[x].fa].son[T[T[x].fa].son[] == y]=x;
T[x].son[p]=y;
T[y].fa=x;
PushUp(y);
PushUp(x);
} void Splay(int x, int To) //将x节点移动到To的子节点中
{
while(T[x].fa != To)
{
if(T[T[x].fa].fa == To)
Rotate(x, T[T[x].fa].son[] == x);
else
{
int y=T[x].fa, z=T[y].fa;
int p=(T[z].son[] == y);
if(T[y].son[p] == x)
Rotate(x, !p), Rotate(x, p); //之字旋
else
Rotate(y, p), Rotate(x, p); //一字旋
}
}
if(To == ) rt=x;
} int GetPth(int p, int To) //返回第p小的节点 并移动到To的子节点中
{
if(!rt || p > T[rt].size) return ;
int x=rt;
while(x)
{
PushDown(x);
if(p >= T[T[x].son[]].size+ && p <= T[T[x].son[]].size+T[x].num)
break;
if(p > T[T[x].son[]].size+T[x].num)
{
p-=T[T[x].son[]].size+T[x].num;
x=T[x].son[];
}
else
x=T[x].son[];
}
Splay(x, );
return x;
} int Find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处
{
if(!rt) return ;
int x=rt;
while(x)
{
PushDown(x);
if(T[x].key == key) break;
x=T[x].son[key > T[x].key];
}
if(x) Splay(x, );
return x;
} int Prev() //返回根节点的前驱 非重点
{
if(!rt || !T[rt].son[]) return ;
int x=T[rt].son[];
while(T[x].son[])
{
PushDown(x);
x=T[x].son[];
}
Splay(x, );
return x;
} int Succ() //返回根结点的后继 非重点
{
if(!rt || !T[rt].son[]) return ;
int x=T[rt].son[];
while(T[x].son[])
{
PushDown(x);
x=T[x].son[];
}
Splay(x, );
return x;
} void Insert(int key) //插入key值
{
if(!rt)
rt=Newnode(key, );
else
{
int x=rt, y=;
while(x)
{
PushDown(x);
y=x;
if(T[x].key == key)
{
T[x].num++;
T[x].size++;
break;
}
T[x].size++;
x=T[x].son[key > T[x].key];
}
if(!x)
x=T[y].son[key > T[y].key]=Newnode(key, y);
Splay(x, );
}
} void Delete(int key) //删除值为key的节点1个
{
int x=Find(key);
if(!x) return;
if(T[x].num>)
{
T[x].num--;
PushUp(x);
return;
}
int y=T[x].son[];
while(T[y].son[])
y=T[y].son[];
int z=T[x].son[];
while(T[z].son[])
z=T[z].son[];
if(!y && !z)
{
rt=;
return;
}
if(!y)
{
Splay(z, );
T[z].son[]=;
PushUp(z);
return;
}
if(!z)
{
Splay(y, );
T[y].son[]=;
PushUp(y);
return;
}
Splay(y, );
Splay(z, y);
T[z].son[]=;
PushUp(z);
PushUp(y);
} int GetRank(int key) //获得值<=key的节点个数
{
if(!Find(key))
{
Insert(key);
int tmp=T[T[rt].son[]].size;
Delete(key);
return tmp;
}
else
return T[T[rt].son[]].size+T[rt].num;
} void Delete(int l, int r) //删除值在[l, r]中的所有节点 l!=r
{
if(!Find(l)) Insert(l);
int p=Prev();
if(!Find(r)) Insert(r);
int q=Succ();
if(!p && !q)
{
rt=;
return;
}
if(!p)
{
T[rt].son[]=;
PushUp(rt);
return;
}
if(!q)
{
Splay(p, );
T[rt].son[]=;
PushUp(rt);
return;
}
Splay(p, q);
T[p].son[]=;
PushUp(p);
PushUp(q);
}

相关题目:HNOI 2002 POJ3481 POJ2352 POJ1442

NOI2004 郁闷的出纳员

II 用于维护序列: (以序列下标为对象维护,相当于对区间操作)(能够完成线段树的操作及其不能完成的操作)

  Struct Tree{

 int key, sum, size, fa, son[];

 }

 支持操作:

 void PushUp(int x);

 void PushDown(int x);

 int MakeTree(int l, int r, int a[]); //新建一个子树返回根节点

 void Rotate(int x, int p); //0左旋 1右旋

 void Splay(int x, int To); //将x节点移动到To的子节点中

 int Select(int p, int To); //将第p个数移动到To的子节点中 并返回该节点

 int Find(int key); //返回值为key的节点 若无返回0 若有将其转移到根处

 int Prev(); //返回根节点的前驱

 int Succ(); //返回根结点的后继

 void Insert(int p, int l, int r, int a[]) //将a[l .. r]的数插入到下标为p后面

 void Delete(int l, int r); //删除区间[l, r]中的节点

 int Query(int l, int r); //返回[l, r]的和

 待补充。。

 Size Balance Tree

 和上述两种二叉树比起来,SBT可能是最像真正平衡二叉树吧。

 SBT能够保证树的高度在lgn,这样对于插入,删除操作都能够准确保证时间复杂度在O(lgn)

 Maintain操作事实上理解起来也是挺简单的,至于证明参见CQF神牛的 《SBT》 

模版:

 int cnt, rt;

 struct Tree
{
int key, size, son[];
}T[MAXN]; inline void PushUp(int x)
{
T[x].size=T[T[x].son[]].size+T[T[x].son[]].size+;
} inline int Newnode(int key)
{
++cnt;
T[cnt].key=key;
T[cnt].size=;
T[cnt].son[]=T[cnt].son[]=;
return cnt;
} void Rotate(int p, int &x)
{
int y=T[x].son[!p];
T[x].son[!p]=T[y].son[p];
T[y].son[p]=x;
PushUp(x);
PushUp(y);
x=y;
} void Maintain(int &x, int p) //维护SBT的!p子树
{
if(T[T[T[x].son[p]].son[p]].size > T[T[x].son[!p]].size)
Rotate(!p, x);
else if(T[T[T[x].son[p]].son[!p]].size > T[T[x].son[!p]].size)
Rotate(p, T[x].son[p]), Rotate(!p, x);
else return;
Maintain(T[x].son[], );
Maintain(T[x].son[], );
Maintain(x, );
Maintain(x, );
} inline int Prev() //返回比根值小的最大值 若无返回0
{
int x=T[rt].son[];
if(!x) return ;
while(T[x].son[])
x=T[x].son[];
return x;
} inline int Succ() //返回比根值大的最小值 若无返回0
{
int x=T[rt].son[];
if(!x) return ;
while(T[x].son[])
x=T[x].son[];
return x;
} void Insert(int key, int &x)
{
if(!x) x=Newnode(key);
else
{
T[x].size++;
Insert(key, T[x].son[key > T[x].key]);
Maintain(x, key > T[x].key);
}
} bool Delete(int key, int &x) //删除值为key的节点 key可以不存在
{
if(!x) return ;
if(T[x].key == key)
{
if(!T[x].son[])
{
x=T[x].son[];
return ;
}
if(!T[x].son[])
{
x=T[x].son[];
return ;
}
int y=Prev();
T[x].size--;
return Delete(T[x].key, T[x].son[]);
}
else
if(Delete(key, T[x].son[key > T[x].key]))
{
T[x].size--;
return ;
}
} int GetPth(int p, int &x) //返回第p小的节点
{
if(!x) return ;
if(p == T[T[x].son[]].size+)
return x;
if(p > T[T[x].son[]].size+)
return GetPth(p-T[T[x].son[]].size-, T[x].son[]);
else
return GetPth(p, T[x].son[]);
} int GetRank(int key, int &x) //找出值<=key的节点个数
{
if(!x) return ;
if(T[x].key <= key)
return T[T[x].son[]].size++GetRank(key, T[x].son[]);
else
return GetRank(key, T[x].son[]);
}

相关题目:POJ 3481

上述题均为用于测试平衡树基本操作的题目。

提高题:

[NOI2005]维修数列

[POJ3580]SuperMemo

[HNOI2004]宠物收养所

在文章的最后贴上一个二叉树专题训练https://vjudge.net/contest/84416;jsessionid=E73DCD38F70FF141A029A2DB5958B2F1

喜欢的点个赞并订阅我们,我们将会提供最优质的文章供大家学习参考,欢迎大家一起学习QAQ

上一篇:.NetDOM操作--un


下一篇:三大平衡树(Treap + Splay + SBT)总结+模板[转]