本蒟蒻最近刚刚学会平衡树,特来写篇博客以加深印象

(我的意思是若写的不好望各位奆佬多多包含!)

题目描述

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

  1. 插入 x 数
  2. 删除 x 数(若有多个相同的数,因只删除一个)
  3. 查询 x 数的排名(排名定义为比当前数小的数的个数 +1 。若有多个相同的数,因输出最小的排名)
  4. 查询排名为 x 的数
  5. 求 x 的前驱(前驱定义为小于 x ,且最大的数)
  6. 求 x 的后继(后继定义为大于 x ,且最小的数)

输入输出格式

输入格式:

 

第一行为 n ,表示操作的个数,下面 n 行每行有两个数 opt 和 x , opt 表示操作的序号

 

输出格式:

 

对于操作 3,4,5,6 每行输出一个数,表示对应答案

 

输入输出样例

输入样例#1: 

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

输出样例#1: 

106465
84185
492737

样例是真的大啊!=_=

大的都不像是样例了!

好了,现在开始讲解!

首先讲解我用的变量吧!!

int ch[maxn][2] ;//存儿子,ch[][0]存左儿子,ch[][1]存右儿子
int f[maxn] ;//存爹
int size[maxn] ;//存这个点的子树大小
int cnt[maxn] ;//存权值
int key[maxn] ;//存数值
int sz,root ;//整棵树的大小和树根

首先,一切从简单的开始讲起,首先说输入(不想看的向下翻)

首先输入一个数n,然后下面n行,每行输入一个操作标记和数。

int n,opt,x;
    scanf("%d",&n);
    for (int i=1;i<=n;++i){
        scanf("%d%d",&opt,&x);
        switch(opt){
            case 1: 插入
            case 2: 删除
            case 3: 找数的排名
            case 4: 找排名的数
            case 5: 找前驱
            case 6: 找后继
        }
    }

然后在依次讲解操作

操作1:插入

以我之见,插入这个是最容易打错的操作(我就打错了好几次)。 

总体的思路是:如果遇到一个与x数值相同的数,就把数的权值加一。

还有一些特殊的情况:

1.如果插入时树为空树:那么就把整棵树的长度加一,因为只有一个点,所以要给他的左右儿子赋值为0 ;

2.如果插入时已经到了树的最底端(也没有找到),那么就可以直接插入。

具体见代码,代码如下:

void insert(int x){//插入操作
	if(root == 0) {//如果当前树为空树
		sz ++ ;//整棵树的长度加一
		ch[sz][0] = ch[sz][1] = f[sz] = 0 ;//两个儿子和爸爸都没有
		root = sz ;//此时树根就是插入的这个数
		size[sz] = cnt[sz] = 1 ;//权值和子树大小都是1 
		key[sz] = x ;//当前点的data赋值为要插入的数
		return ;
	}
	int now = root , fa = 0 ;
	while(true){
		if(key[now] == x ){//如果遇到一个节点的数值和要插入的值相同
			cnt[now] ++ ;//x的权值++
			update(now) ;//数值更新
			update(fa) ;
			splay(now) ;
			break ;
		}
		fa = now ;
		if(key[now] < x) now = ch[now][1] ;//如果数值比当前点的数字大,找右儿子
		else now = ch[now][0] ;//反之,找左儿子
		if(now == 0){//如果到了树底
			sz ++ ;//直接插入,处理方法和空树类似
			ch[sz][0] = ch[sz][1] = 0 ;
			f[sz] = fa ;
			size[sz] = cnt[sz] = 1 ;
			if(key[fa] < x ) ch[fa][1] = sz ;//处理应插入的地方
			else ch[fa][0] = sz ;  
			key[sz] = x ;
			update(fa) ;
			splay(sz) ;
			break ;
		}
	}
}

PS:代码里好像有很多函数,像update和splay,这些在文章的最后面会给出代码 QwQ,只知道update是更新数值,splay是b把括号里的节点旋转到根的位置就可以了!!QwQ

操作2:删除

删除在我看来无异于大模拟 ,也许就是个大模拟吧!!

删除,简单来说,就是把这一个节点的data(儿子,父亲,祖宗)给clear(清除)掉

但是,这个还是分好多好多的情况的啊!

1.如果有不少相同的数,那么就随便踢掉一个

2.如果要删得数没有孩子,那么就直接删掉(毕竟没有孩子没有多余的牵挂啥的

3.如果只有一个独生子,那么就要学一下檀黎斗神的操作,干掉自己的爸爸,自己当爸爸!!

最后捏,我们只要改变各个父子关系,好让要删数的data销声匿迹就好了!

然后就是代码:

void del(int x){
    int L_Y_T = find(x) ;//此操作的目的只是吧x旋到树根……
    if(cnt[root]>1){//如果有很多个x
        cnt[root] -- ;//随便踢掉一个
        update(root) ;//更新数值
        return ;
    }
    if(!ch[root][0] && !ch[root][1]) {//如果无儿无女
        clear(root) ;//直接放进回收站
        root = 0 ;//当然没根了(因为L_Y_T让x当根了啊)
        return ;
    }
    if(!ch[root][0]){如果只有右儿子(没有左儿子且有儿子)
        int oldroot = root ;//将当前根存一下
        root = ch[root][1] ;//让他仅有的右儿子当根
        f[root] = 0 ;//根是右儿子了,所以右儿子就没爹了
        clear(oldroot) ;//清空垃圾数据
        return ;
    }
    if(!ch[root][1]){//如果只有左儿子(没有右儿子且有儿子)
        int oldroot = root ;//同上
        root = ch[root][0] ;//同上
        f[root] = 0 ;//同上
        clear(oldroot) ;//同上
        return ;
    }
    int leftbig = pre() , oldroot = root ;找到新根(数的前驱),然后保存旧根
    splay(leftbig) ;//让新根当根
    ch[root][1] = ch[oldroot][1] ;//把原来x的右儿子接到新根上。
    f[ch[oldroot][1]] = root ;//这样就吧x彻底删了QWQ
    clear(oldroot) ;//删除废物数据
    update(root) ;//更新数据
}

PS:clear和pre也是个函数,意思很常规,后面有代码。

操作3:查询x排名

如果x比当前的节点小,那么就去左子树找

反之,去右子树找

如果相等的话怎么办??

如果相等的话就停下啊还怎么办!!

好吧,不皮了

<code>

int find(int x){
	int now = root , ans = 0 ;//初始化,一定要的
	while(true){
		if(x < key[now]) //如果x比当前数值小
		now = ch[now][0] ;//搭乘去左子树的高铁=_=
		else//否则就跑右子树
		{
			if(ch[now][0])//如果有左子树,也就是在你前面还有别的 
			ans += size[ch[now][0]] ;//那么就加上左子树的数值
            //是不是对于上面的几行有人已经W_W了??
            //讲解一下:由于左子树总是小于根小于右子树
            //所以,因为是排名嘛,比如说10分的有3个人,1分的有一个,100分的有一个且一共只有这些成绩,那么你考了99分就只排在100后面,但是如果你考了9分的话就只有排名5了,因为有3个10分,简而言之,你考的高没人管你,但你考的低就是个问题了!!!!
			if(x == key[now]){//如果找到了
				splay(now) ;//那么就转一下
				return ans + 1 ;
			}
			ans += cnt[now] ;
			now = ch[now][1] ;
		}
	}
}

操作4:找到排名为x的节点

这个说实话烦人啊!操作3和操作4看的我是眼花缭乱啊!QwQ~~我太弱了~~QwQ  T~T 

 和上面的思想差不多~~

如果当前点有左子树,且x比左子树的权值(占得排名)小的话,就搭乘前往左子树的列车。

反之,就去右子树。

<code>

int findx(int x){//操作4 找到排名为x的点
    int now = root ;//照样存根
    while(1)
    {
        if(ch[now][0] && x <= size[ch[now][0]])//如果有左子树并且x比左子树的权值(占得排名)小 
        now = ch[now][0] ;//去左子树玩
           else
         {
             int temp = (ch[now][0]?size[ch[now][0]]:0) + cnt[now] ; //精髓(这个不好翻译QwQ),找排名嘛!和find()一样,如果有左子树就加上左子树占得排名(如果没有就不干了呗!);
             if(x <= temp) return key[now] ;
             x -= temp ;
             now = ch[now][1] ; 
         }
    }
}

操作5:找前驱

操作6:找后继(狠心遗弃)

看了这么久,大家伙会发现,右子树>根>左子树的小规律,所以,前驱就是最左边的点 ,同理,后继就是最右边的点喽!!

int pre(){
    int now = ch[root][0] ;
    while(ch[now][1]) now = ch[now][1] ;
    return now ;
}

好了,我们现在基本操作都讲完了,现在该叙述一下中间涉及到的函数了

function1:clear(int x)

只用于将点删除后的清零小工作~~

<code>

void clear(int x){
	ch[x][0] = ch[x][1] = size[x] = cnt[x] = key[x] = f[x] = 0 ;//各项清零
}

很简单,没啥好讲的

function2:get(int x)

作用就是查询x是左儿子还是右儿子。

 <code>

int get(int x){
	return ch[f[x]][1] == x ;
}
/*
讲解一下:(其实都能看懂吧~~)
如果x爹的右儿子是x的话,就返回1
如果x爹的右儿子不是x的话,也就是x是x爹的做儿子的话,返回0
*/

function3 :update(int x )

唯一用途:修改后更新数值

code

void update(int x)
{
	if(x){
		size[x] = cnt[x] ;
		if(ch[x][0]) size[x] += size[ch[x][0]] ;
		if(ch[x][1]) size[x] += size[ch[x][1]] ;
	}
}

也比较简单,于是就不住释了~~~

function4:rotate(int x)

这个可是平衡树的重点大戏

rotate没理解好就和输出输出错了一个效果!!QwQ、

具体思路:首先找到x关于x爹的关系,记做k关系(用get())

然后 将x与k关系相反的儿子 的父亲 记做与(x爹)关系相同的儿子

然后再将和x关系相反的儿子  的父亲  记做  x爹 的父亲

将x爹的父亲记做x

将x与k关系相反的儿子  记做  x爹

将x的父亲记做x爹的父亲(也就是x的爷爷)

有点混乱是不是呀??!!

正常,看看代码,自己画画图就好了!!!

<code>

void rotate(int x){//旋转操作
	int old = f[x] , oldf = f[f[x]] ;//定义 old 为 x爹 , oldf 为 x爷
	int k = get(x) ;// 关系
	ch[old][k] = ch[x][!k] ;//x爹的k儿子为x的!k儿子
	f[ch[old][k]] = old ;//x的!k儿子的爹记为x爹(夭寿了!改爹了!!)
	ch[x][!k] = old ;//x的!k儿子 为 x自己的爹
	f[old] = x ;
	f[x] = oldf ;
	if(oldf){//判断自己有没有新的爸
		if(ch[oldf][1] == old) ch[oldf][1] = x ;//如果有新的爸爸,且右儿子是x爹(x叛变之前的爹),那么x成为自己爷爷的新右儿子(因为x爹已经成了x的儿子了)
		else
		ch[oldf][0] = x ;
	}
	update(old) ;update(x) ;//更新数字
}

function5 : splay(int x)

就是多次的rotate喽!

直接看《code》 吧

void splay(int x)
{
	for(int fa;fa = f[x] ;rotate(x)) {//玩命旋转
		if(f[fa]){
			if(get(x) == get(fa))//特殊情况:三点共线(三代共线)
			rotate(fa) ;//先旋转爸
			else
			rotate(x) ;//先旋转自己
		}
	} 
	root = x ;
}

完结散花!!!! 

啥??完整代码??
把上面组合一下应该就是了吧……………………