首页 > 其他分享 >[笔记]AVL树

[笔记]AVL树

时间：2024-06-16 15:54:51浏览次数：23  
标签：avl int siz void 笔记 else AVL hei

AVL树是一种严格平衡的二叉搜索树，任何操作结束后，都能保证每个节点的左右子树高度相差不超过\(1\)。
内容源自BV1rt411j7Ff - 【AgOHの数据结构】平衡树专题之叁 树旋转与AVL树。

模板题：P3369 【模板】普通平衡树。

结构体定义 & 基本函数

struct node{
	int l;//左孩子
    int r;//右孩子
    int v;//值
    int hei;//高度，叶节点为1
    int siz;//大小
}avl[N];
int cnt;//当前用到哪一个节点了，用于新建节点
int root;//根节点

//新建节点
void newnode(int &u,int v){
	avl[u=++cnt].v=v;//赋值
	avl[cnt].siz=1;//叶子节点
}

//更新节点信息
void update(int u){
	avl[u].siz=avl[avl[u].l].siz+avl[avl[u].r].siz+1;//左+右+1
	avl[u].hei=max(avl[avl[u].l].hei,avl[avl[u].r].hei)+1;//max(左,右)+1
}

左右旋转

AVL树用旋转来维护树的平衡。旋转分左旋和右旋：

//左旋
void lrot(int &u){
	int r=avl[u].r;
	avl[u].r=avl[r].l;
	avl[r].l=u;
	u=r;
	update(avl[u].l),update(u);
}
//右旋
void rrot(int &u){
	int l=avl[u].l;
	avl[u].l=avl[l].r;
	avl[l].r=u;
	u=l;
	update(avl[u].r),update(u);
}

接下来我们需要判断并处理AVL树的不平衡情况。

//计算平衡因子（即左子树高度-右子树高度）
int factor(int u){
	return avl[avl[u].l].hei-avl[avl[u].r].hei;
}

对于树上的节点\(u\)（假定\(u\)的子树都平衡），其不平衡状态有\(4\)种：

  • LL：\(u\)的左子树过高，而左子节点的左子树较高。
    处理方法：右旋一次\(u\)。
  • LR：\(u\)的左子树过高，而左子结点的右子树较高。
    处理方法：设\(v\)是\(u\)的左儿子，先左旋\(v\)（转化成LL），再右旋\(u\)。
  • RR：\(u\)的右子树过高，而右子节点的右子树较高。
    处理方法：左旋一次\(u\)。
  • RL：\(u\)的右子树过高，而右子节点的左子树较高。
    处理方法：设\(v\)是\(u\)的右儿子，先右旋\(v\)（转化成RR），再左旋\(u\)。

若左子节点的左右子树高度相同，则既可以归纳为LL，也可以作为LR考虑。右子节点同理。

//检查并调整为平衡状态，并更新节点的信息
void check(int &u){
	int uf=factor(u);
	if(uf>1){
		int lf=factor(avl[u].l);
		if(lf>0) rrot(u);//LL
		else lrot(avl[u].l),rrot(u);//LR
	}else if(uf<-1){
		int rf=factor(avl[u].r);
		if(rf<0) lrot(u);//RR
		else rrot(avl[u].r),lrot(u);//RL
	}else if(u) update(u);//如果原本就平衡，且u不为空，就要更新
}

其他操作

和普通的BST一样了。

//插入
void ins(int &u,int v){
	if(!u) newnode(u,v);
	else if(v<avl[u].v) ins(avl[u].l,v);
	else ins(avl[u].r,v);
	check(u);//自下向上更新节点信息&调整结构
}

//找u的后继（即u先往右走，再不断往左直到没有左子结点）v，
//让v的父节点直接连接v的右子树
int find(int &u,int fa){
	int ans;
	if(!avl[u].l){//终点
		ans=u;
		avl[fa].l=avl[u].r;
	}else{
		ans=find(avl[u].l,u);
		check(u);
	}
	return ans;
}
//删除
void del(int &u,int v){
	if(v==avl[u].v){
		int l=avl[u].l,r=avl[u].r;
		if(!l||!r) u=l+r;
		else{
			u=find(r,r);//u的后继v来替代u的位置
			avl[u].l=l;//v成为子树的根，连接左边
			if(u!=r) avl[u].r=r;//连接右边
		}
	}else if(v<avl[u].v) del(avl[u].l,v);
	else del(avl[u].r,v);
	check(u);//自下向上更新节点信息&调整结构
}

//计算v的排名（小于v的个数+1）
int getrank(int v){
	int u=root,ran=1;
	while(u){
		if(v<=avl[u].v) u=avl[u].l;
		else{
			ran+=avl[avl[u].l].siz+1;
			u=avl[u].r;
		}
	}
	return ran;
}

//计算第ran名
int getnum(int ran){
	int u=root;
	while(u){
		if(avl[avl[u].l].siz+1==ran) break;
		else if(avl[avl[u].l].siz>=ran)
			u=avl[u].l;
		else
			ran-=avl[avl[u].l].siz+1,u=avl[u].r;
	}
	return avl[u].v;
}

//前驱
int pre(int x){return getnum(getrank(x)-1);}
//后继
int nex(int x){return getnum(getrank(x+1));}

Code

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
struct node{
	int l,r,v,hei,siz;
}avl[N];
int t,cnt,root;
void newnode(int &u,int v){
	avl[u=++cnt].v=v;
	avl[cnt].siz=1;
}
void update(int u){
	avl[u].siz=avl[avl[u].l].siz+avl[avl[u].r].siz+1;
	avl[u].hei=max(avl[avl[u].l].hei,avl[avl[u].r].hei)+1;
}
int factor(int u){
	return avl[avl[u].l].hei-avl[avl[u].r].hei;
}
void lrot(int &u){
	int r=avl[u].r;
	avl[u].r=avl[r].l;
	avl[r].l=u;
	u=r;
	update(avl[u].l),update(u);
}
void rrot(int &u){
	int l=avl[u].l;
	avl[u].l=avl[l].r;
	avl[l].r=u;
	u=l;
	update(avl[u].r),update(u);
}
void check(int &u){
	int uf=factor(u);
	if(uf>1){
		int lf=factor(avl[u].l);
		if(lf>=0) rrot(u);//LL
		else lrot(avl[u].l),rrot(u);//LR
	}else if(uf<-1){
		int rf=factor(avl[u].r);
		if(rf<=0) lrot(u);//RR
		else rrot(avl[u].r),lrot(u);//RL
	}else if(u) update(u);
}
void ins(int &u,int v){
	if(!u) newnode(u,v);
	else if(v<avl[u].v) ins(avl[u].l,v);
	else ins(avl[u].r,v);
	check(u);
}
int find(int &u,int fa){
	int ans;
	if(!avl[u].l){//终点
		ans=u;
		avl[fa].l=avl[u].r;
	}else{
		ans=find(avl[u].l,u);
		check(u);
	}
	return ans;
}
void del(int &u,int v){
	if(v==avl[u].v){
		int l=avl[u].l,r=avl[u].r;
		if(!l||!r) u=l+r;
		else{
			u=find(r,r);//找u的后继，即比u大的第一个数
			avl[u].l=l;
			if(u!=r) avl[u].r=r;
		}
	}else if(v<avl[u].v) del(avl[u].l,v);
	else del(avl[u].r,v);
	check(u);
}
int getrank(int v){
	int u=root,ran=1;
	while(u){
		if(v<=avl[u].v) u=avl[u].l;
		else{
			ran+=avl[avl[u].l].siz+1;
			u=avl[u].r;
		}
	}
	return ran;
}
int getnum(int ran){
	int u=root;
	while(u){
		if(avl[avl[u].l].siz+1==ran) break;
		else if(avl[avl[u].l].siz>=ran)
			u=avl[u].l;
		else
			ran-=avl[avl[u].l].siz+1,u=avl[u].r;
	}
	return avl[u].v;
}
int pre(int x){return getnum(getrank(x)-1);}
int nex(int x){return getnum(getrank(x+1));}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>t;
	while(t--){
		int op,x;
		cin>>op>>x;
		if(op==1) ins(root,x);
		else if(op==2) del(root,x);
		else if(op==3) cout<<getrank(x)<<"\n";
		else if(op==4) cout<<getnum(x)<<"\n";
		else if(op==5) cout<<pre(x)<<"\n";
		else if(op==6) cout<<nex(x)<<"\n";
	}
	return 0;
}

附：相同节点合并写法

当时看完视频，想到是不是能把相同节点计数，存在一个节点中。

于是就写出下面的代码了。结构体多存了一个\(cnt\)，然后newnode、update、ins、del、getrank、getnum函数需要做相应的修改。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
struct node{
	int l,r,v,hei,siz,cnt;
}avl[N];
int t,cnt,root;
void newnode(int &u,int v){
	avl[u=++cnt].v=v;
	avl[cnt].siz=1;
	avl[cnt].cnt=1;
}
void update(int u){
	avl[u].siz=avl[avl[u].l].siz+avl[avl[u].r].siz+avl[u].cnt;
	avl[u].hei=max(avl[avl[u].l].hei,avl[avl[u].r].hei)+1;
}
int factor(int u){
	return avl[avl[u].l].hei-avl[avl[u].r].hei;
}
void lrot(int &u){
	int r=avl[u].r;
	avl[u].r=avl[r].l;
	avl[r].l=u;
	u=r;
	update(avl[u].l),update(u);
}
void rrot(int &u){
	int l=avl[u].l;
	avl[u].l=avl[l].r;
	avl[l].r=u;
	u=l;
	update(avl[u].r),update(u);
}
void check(int &u){
	int uf=factor(u);
	if(uf>1){
		int lf=factor(avl[u].l);
		if(lf>=0) rrot(u);//LL
		else lrot(avl[u].l),rrot(u);//LR
	}else if(uf<-1){
		int rf=factor(avl[u].r);
		if(rf<=0) lrot(u);//RR
		else rrot(avl[u].r),lrot(u);//RL
	}else if(u) update(u);
}
void ins(int &u,int v){
	if(!u) newnode(u,v);
	else if(v==avl[u].v) avl[u].cnt++;
	else if(v<avl[u].v) ins(avl[u].l,v);
	else ins(avl[u].r,v);
	check(u);
}
int find(int &u,int fa){
	int ans;
	if(!avl[u].l){//终点
		ans=u;
		avl[fa].l=avl[u].r;
	}else{
		ans=find(avl[u].l,u);
		check(u);
	}
	return ans;
}
void del(int &u,int v){
	if(v==avl[u].v){
		if(avl[u].cnt>1) avl[u].cnt--;
		else{
			int l=avl[u].l,r=avl[u].r;
			if(!l||!r) u=l+r;
			else{
				u=find(r,r);//找u的后继，即比u大的第一个数
				avl[u].l=l;
				if(u!=r) avl[u].r=r;
			}
		}
	}else if(v<avl[u].v) del(avl[u].l,v);
	else del(avl[u].r,v);
	check(u);
}
int getrank(int v){//小于自己的个数+1
	int u=root,ran=1;
	while(u){
		if(v<=avl[u].v) u=avl[u].l;
		else{
			ran+=avl[avl[u].l].siz+avl[u].cnt;
			u=avl[u].r;
		}
	}
	return ran;
}
int getnum(int ran){
	int u=root;
	while(u){
		if(avl[avl[u].l].siz+1<=ran&&ran<=avl[avl[u].l].siz+avl[u].cnt) break;
		//如果ran在[siz[l]+1,siz[l]+cnt[u]]的区间内，就说明第ran名就是u
		else if(avl[avl[u].l].siz>=ran)
			u=avl[u].l;
		else
			ran-=avl[avl[u].l].siz+avl[u].cnt,u=avl[u].r;
	}
	return avl[u].v;
}
int pre(int x){return getnum(getrank(x)-1);}
int nex(int x){return getnum(getrank(x+1));}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>t;
	while(t--){
		int op,x;
		cin>>op>>x;
		if(op==1) ins(root,x);
		else if(op==2) del(root,x);
		else if(op==3) cout<<getrank(x)<<"\n";
		else if(op==4) cout<<getnum(x)<<"\n";
		else if(op==5) cout<<pre(x)<<"\n";
		else if(op==6) cout<<nex(x)<<"\n";
	}
	return 0;
}

两种写法效率相当，不合并183ms，合并190ms。
似乎相同节点合并反而更慢？

标签：avl,int,siz,void,笔记,else,AVL,hei
From： https://www.cnblogs.com/Sinktank/p/18249081

相关文章

  • 【机器学习与R语言】系列笔记
    几年前做的机器学习与R语言相关笔记，迁移到公号记录之。1-机器学习简介2-懒惰学习K近邻（KNN）3-概率学习朴素贝叶斯（NB）4-决策树5-规则学习算法6-线性回归7-回归树和模型树8-神经网络9-支持向量机10-关联规则11-Kmeans聚类12-如何评估模型的性能？13-如何提高模型的性能？......
  • 大道至简阅读笔记05
    个人感受我写的代码，总是太复杂就是没有章序，内容繁杂，效率低下，时间成本高。书中提到了这一点，并且书的主要核心就是大道至简，再简单的制作下，完成高质量的任务解决问题方法：学习书中的简约的实践方法，软件开发中，简化代码结构、减少不必要的功能。阅读笔记：学习任何东西都得先了解思想......
  • 05大道至简阅读笔记之一
    《大道至简》阅读笔记主题和核心观点《大道至简》是一本探讨简约生活和思维方式的书籍，由作者某某撰写。书中主要探讨了如何通过简化生活和思维方式，达到更高效、更有意义的生活状态。以下是对这本书的阅读笔记：关键观点总结简约生活的重要性：书中强调了简约生活对个人幸福和心......
  • 06大道至简阅读笔记之一
    《大道至简》阅读笔记主题和核心观点《大道至简》是一本探讨简约生活哲学的书籍，由作者某某撰写。书中主要讨论了如何通过简化生活方式和思维模式，达到更高效、更有意义的生活。以下是对这本书的阅读笔记：关键观点总结简约生活的价值：书籍强调了简约生活对个人幸福和心理健康的......
  • 03构建之法阅读笔记之一
    《构建之法》阅读笔记主题和核心观点《构建之法》是一本探讨创新与设计思维的书籍，由作者某某撰写。书中主要讨论了如何通过系统性的方法和跨学科的视角构建新的想法和解决方案，以及如何应对创新过程中的挑战。以下是对这本书的阅读笔记：关键观点总结创新的系统性方法：作者提出......
  • 04构建之法阅读笔记之一
    《构建之法》阅读笔记主题和核心观点《构建之法》是一本关于创新和设计思维的书籍，由作者某某撰写。书中主要探讨了如何通过系统性的方法构建新的想法和解决方案，以及如何将创意转化为实际的成果。以下是对这本书的阅读笔记：关键观点总结系统性创新方法：书中强调了系统性思维在......
  • 构建之法阅读笔记04
    个人感受：问题：自己做的软件只是按照自己的想法来，没有考虑用户的想法，以及其中的最基本的用户没有提出的要求，没有考虑实际的情况。书中提到了用户体验和软件测试这两部分，只有满足用户的体验，才能是好软件。解决方法，在以后的软件制作过程中应该考虑人的感受，注重实际情况，不可一味的追......
  • 构建之法阅读笔记02
    个人感受：认识到自己的编程方法有问题，没有正确的一个编码流程，只是一味的追求写代码，写完就没有事情干了。书中提到了这一点，做一个项目应该有正确的流程，确定好自己下一步该干什么而不是像无头苍蝇一样到处乱撞。解决方法:学习书中第五章的那样方法规划好自己的流程一步一步来。读......
  • 构建之法阅读笔记03
    个人感受：自己的问题：自己对于软件的认识不够，不清楚什么是软件，做一个软件有着多方面的要求以及规定，但是我不太清楚书中提到了许多软件的要求以及规定，以及如何做好一个软件。解决办法：按照书中的方法自己以及自己的团队多多联系这种方法即可读书笔记第六章和第七章第六章：需......
  • （书和笔记）学习JavaScript数据结构与算法（第3版） ([巴西] 洛伊安妮 • 格罗纳)
    书：pan.baidu.com/s/199LHxxIlMixw3gYSY8tyPw?pwd=ywxg提取码：ywxg数据结构与算法基础：介绍了数据结构与算法的基本概念、重要性以及它们在JavaScript中的应用。数组：深入讲解了数组的定义、操作、常用方法及其在JavaScript中的应用，包括多维数组的构建与访问。栈：详细阐述了栈的概......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99