十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
AVL树的定义:一种特殊的二叉搜索树,它能自动维持平衡
专注于为中小企业提供网站设计、成都做网站服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业汾西免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了上千企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。
AVL是发明者的名字缩写:G.M. AdelsonVelskii and E.M. Landis
利用AVL树实现ADT Map,基本上与BST的实现相同,不同之处仅在于二叉树的生成与维护过程
AVL树的实现中,需要对每个节点跟踪“平衡因子balance factor”参数,平衡因子是根据节点的左右子树的高度来定义的,确切地说,是左右子树高度差:
balanceFactor = height(leftSubTree) − height(rightSubTree)
如果平衡因子大于0,称为“左倾left-heavy”,小于零称为“右倾right-heavy”平衡因子等于0,则称作平衡。
如果一个二叉查找树中每个节点的平衡因子都在-1,0,1之间,则把这个二叉搜索树称为平衡树
我们先看看限定平衡因子带来的结果。我们认为,保证树的平衡因子为–1、0 或 1,可以使关键操作获得更好的大O性能
观察上图h=1~4时,总节点数N的变化
h= 1, N= 1
h= 2, N= 2= 1+ 1
h= 3, N= 4= 1+ 1+ 2
h= 4, N= 7= 1+ 2+ 4
观察这个通式,很接近斐波那契数列
定义斐波那契数列
利用 重写
最多搜索次数h和规模N的关系,可以说AVL树的搜索时间复杂度为O(log n)
❖既然AVL平衡树确实能够改进BST树的性能,避免退化情形
❖我们来看看向AVL树插入一个新key,如何才能保持AVL树的平衡性质
❖首先,作为BST,新key必定以叶节点形式插入到AVL树中
叶节点的平衡因子是0,其本身无需重新平衡
但会影响其父节点的平衡因子:
这种影响可能随着其父节点到根节点的路径一直传递上去,直到传递到根节点为止;
或者某个父节点平衡因子被调整到0,不再影响上层节点的平衡因子为止。
• (无论从-1或者1调整到0,都不会改变子树高度)
重新定义_put方法,调整因子
UpdateBalance方法
rebalance重新平衡
主要手段:将不平衡的子树进行旋转rotation视“左倾”或者“右倾”进行不同方向的旋转
同时更新相关父节点引用,更新旋转后被影响节点的平衡因子
如图,是一个“右倾”子树A的左旋转(并保持BST性质)将右子节点B提升为子树的根,将旧根节点A作为新根节点B的左子节点,如果新根节点B原来有左子节点,则将此节点设
置为A的右子节点(A的右子节点一定有空)
更复杂一些的情况:如图的“左倾”子树右旋转,旋转后,新根节点将旧根节点作为右子节点,但是新根节点原来已有右子节点,需要将原有的右子节点重新定位!原有的右子节点D改到旧根节点E的左子节点,同样,E的左子节点在旋转后一定有空
如何调整平衡因子
看看左旋转对平衡因子的影响,保持了次序ABCDE,ACE的平衡因子不变,hA/hC/hE不变,主要看BD新旧关系
拓展 尝试计算树的高度
TreeNode类中添加高度方法
经过复杂的put方法,AVL树始终维持平衡,get方法也始终保持O(log n)高性能
将AVL树的put方法分为两个部分:
需要插入的新节点是叶节点,更新其所有父节点和祖先节点的代价最多为O(log n)
如果插入的新节点引发了不平衡,重新平衡最多需要2次旋转,但旋转的代价与问题规模无关,是常数O(1)所以整个put方法的时间复杂度还是O(log n)
D、树中最大元素一定是无左子树。
因为每个结点的左子树的结点的值比该结点的值小,所以树中最大元素一定是无左子树。
BT退化为每个结点 (非叶) 只有两棵子树时,结点的数目最少,叶子也最少。设层号为i则各层结点数为2^(i-1)个,那么高为h的BT最大层号是j时,有h=j-1。
整个树的结点数为s=2^0+2^1+2^2+…+2^h, 故s=2^(h+1)-1。其叶子的个数是2^h。同理,当BT每个非叶结点都有三棵子数时,结点数目最多。
扩展资料:
任意节点的子树的高度差都小于等于1。常见的符合平衡树的有,B树(多路平衡搜索树)、AVL树(二叉平衡搜索树)等。
平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低,在完成集合的一系列操作中始终保持平衡,为大型数据库的组织、索引提供了一条新的途径。
以前做的。
一、 需求分析
1. 本程序是是利用平衡二叉树实现一个动态查找表,实现动态查找表的三种基本功能:查找、插入和删除。
2. 初始,平衡二叉树为空树,可以按先序输入平衡二叉树,以输入0结束,中间以回车隔开,创建好二叉树后,可以对其查找,再对其插入,输入0结束插入,再可以对其删除,输入0结束,每次插入或删除一个结点后,更新平衡二叉树的显示。
3. 本程序以用户和计算机的对话方式执行,根据计算机终端显示:“提示信息”下,用户可由键盘输入要执行的操作。
4. 测试数据(附后)
二、 概要设计
1. 抽象数据类型动态查找表的定义如下:
ADT DynamicSearchTable{
数据结构D:D是具有相同特性的数据元素的集合。各个数据元素含有类型相同,可惟一标识数据元素的关键字。
数据关系R:数据元素同属一个集合。
基本操作P:
InitDSTable(DT);
操作结果:构造一个空的动态查找表DT。
DestroyDSTable(DT);
初试条件:动态查找表DT存在。
操作结果: 销毁动态查找表DT。
SearchDSTable(DT,key);
初试条件:动态查找表DT存在,key为和关键字类型相同的给定值。
操作结果: 若DT中存在其关键字等于key的数据元素,则函数值为该元素的值或表中的位置,否则为“空”。
InsertDSTable(DT,e);
初试条件:动态查找表DT存在,e为待插入的数据元素。
操作结果: 若DT中不存在其关键字等于e. key的数据元素,则插入e到DT。
DeleteDSTable(DT,key);
初试条件:动态查找表DT存在,key为和关键字类型相同的给定值。
操作结果: 若DT中存在其关键字等于key的数据元素,则删除之。
TraverseDSTable(DT,Visit());
初试条件:动态查找表DT存在,Visit()是结点操作的应用函数。
操作结果: 按某种次序对DT的每个结点调用函数Visit()一次且至多
一次。一但Visit()失败,则操作失败。
}ADT DynamicSearchTable
2. 本程序包含两个模块:
Void main(){
Do{
接受命令(根据提示输入终点城市和起点城市的序号);
处理命令;
}while(“命令”=“退出”);
}
3.本程序只有两个模块,调用关系简单
主程序模块
平衡二叉树的模块
三、 详细设计
1. 根据题目要求和查找的基本特点,其结点类型
typedef struct BSTnode{
int data;
int bf;
struct BSTnode *lchild,*rchild;
}BSTnode,*bstree;
#define LH +1
#define EH 0
#define RH -1
/-----------------------------************对平衡二叉树的操作
bstree InsertAVL(bstree T, int e);
////////在平衡二叉树中插入结点。
int FindAVL(bstree p,int e);
////////查找平衡二叉树中是否有结点e。
bstree DeleteAVL(bstree T,int e)
////////删除平衡平衡二叉树的结点e,并保持平衡二叉树的性质。
int Preordertraverse(bstree T)
////////按先序遍历平衡二叉树。
/------------------------************平衡二叉树的操作的详细算法
bstree InsertAVL(bstree T, int e)
{
bstree p;
//插入新结点,树长高置taller为TRUE
if(!T) {
T=(bstree)malloc(sizeof(BSTnode));
T-data=e;
T-lchild=T-rchild=NULL;
T-bf=EH;
taller=TRUE;
}
else {
//树中存在和e有相同关键字的结点则不再插入
if(e==T-data){
taller=FALSE;
return NULL;
}
//值小于则继续在树的左子树中搜索
if(e T-data){
//插入到左子树且左子树长高
p=InsertAVL(T-lchild,e);
if(p){
T-lchild=p;
if(taller) {
switch(T-bf){ //检查*T的平衡度
case LH: //原本左子树比右子树高,需要做左平衡处理
T=LeftBalance(T);
taller=FALSE;
break;
case EH: //原本左子树和右子树同高,现因左子树争高而使树增高
T-bf=LH;
taller=TRUE;
break;
case RH: //原本右子树比左子树高,现在左右子树等高
T-bf=EH;
taller=FALSE;
break;
}///////switch(T-bf)
}///////if(taller)
}/////if(p)
}///////if(e T-data)
//继续在*T的右子树中搜索
else{
//插入到右子树且使右子树长高
p=InsertAVL(T-rchild,e);
if (p){
T-rchild=p;
if(taller) {
switch(T-bf){ //检查*T的平衡度
case LH: //原本左子树比右子树高,现在左右子树等高
T-bf=EH;
taller=FALSE;
break;
case EH: //原本左子树和右子树同高,现因右子树增高而使树增高
T-bf=RH;
taller=TRUE;
break;
case RH: //原本右子树比左子树高,需要做右平衡处理
T=RightBalance(T);
taller=FALSE;
break;
}//////switch(T-bf)
}/////if(taller)
}/////if (p)
}//////if(e T-data)
}///////else
return T;
}
int Preordertraverse(bstree T){
if(T){
printf(" %d %d\n",T-data,T-bf);
Preordertraverse(T-lchild);
Preordertraverse(T-rchild);
}
return 1;
}
int FindAVL(bstree p,int e){
if(p==NULL)return NULL;
else if(e==p-data) return true;
else if(ep-data){
p=p-lchild;
return FindAVL(p, e);
}////左子树上查找
else {
p=p-rchild;
return FindAVL( p, e);
}////右子树上查找
}
bstree DeleteAVL(bstree T,int e){
//删除后要保证该二叉树还是平衡的
int n,m=0;/////标记
bstree q;
if(!T)return NULL;
else {
if(e==T-data) {////直接删除
n=Delete(T,e);
m=n;
if(m!=0) {
q=T;
DeleteAVL(T,m);
q-data=m;}
}
else {
if(eT-data){////在左子树上寻找
DeleteAVL(T-lchild,e);
if(shorter){
switch(T-bf){
case LH:T-bf=EH;shorter=true;break;
case EH:T-bf=RH;shorter=false;break;
case RH:Delete_Rightbalance(T);shorter=true;break;
}////switch(T-bf)
}/////if(shorter)
}/////if(eT-data)
else{ /////////在右子树上寻找
DeleteAVL(T-rchild,e);
if(shorter)
switch(T-bf){
case LH:Delete_Leftbalance(T);shorter=true;break;
case EH:T-bf=LH;shorter=false;break;
case RH:T-bf=EH;shorter=true;break;
}////////switch(T-bf)
}////////在右子数上寻找完
}////////在左右子上完
}///////////删除完
return T;
}
2. 主程序和其他伪码算法
void main(){
while(e!=0){
if(e!=0) InsertAVL(T,e);
}
while(d!=0){
if(d!=0) InsertAVL(T,d);
Preordertraverse(T);
}
c=FindAVL(T,t);
if(c==1)printf("有要查找的节点\n");
else printf("无要查找的节点\n");
do{
DeleteAVL(T,b);
Preordertraverse(T);
}while(b==1);
}
///右旋
bstree R_Rotate(bstree p){
bstree lc;
lc=p-lchild;
p-lchild=lc-rchild;
lc-rchild=p;
p=lc;
return p;
}
////左旋
bstree L_Rotate(bstree p){
bstree rc;
rc=p-rchild;
p-rchild=rc-lchild;
rc-lchild=p;
p=rc;
return p;
}
/////左平衡处理
bstree LeftBalance(bstree T){
bstree lc,rd;
lc=T-lchild; //lc指向*T的左子树根结点
switch(lc-bf) { //检查*T的左子树平衡度,并做相应的平衡处理
case LH: //新结点插入在*T的左孩子的左子树上,要做单右旋处理
T-bf=lc-bf=EH;
T=R_Rotate(T);
break;
case RH: //新结点插入在*T的左孩子的右子树上,要做双旋处理
rd=lc-rchild; //rd指向*T的左孩子的右子树根
switch(rd-bf){ //修改*T及其左孩子的平衡因子
case LH:
T-bf=RH;
lc-bf=EH;
break;
case EH:
T-bf=lc-bf=EH;
break;
case RH:
T-bf=EH;
lc-bf=LH;
break;
}//////////switch(rd-bf)
rd-bf=EH;
T-lchild=L_Rotate(T-lchild); //对*T的左孩子做左旋平衡处理
T=R_Rotate(T); //对*T做右旋处理
}////////switch(lc-bf)
return T;
}
////右平衡处理
bstree RightBalance(bstree T)
{
bstree rc,ld;
rc=T-rchild; //rc指向*T的右子树根结点
switch(rc-bf) { //检查*T的右子树平衡度,并做相应的平衡处理
case RH: //新结点插入在*T的右孩子的右子树上,要做单右旋处理
T-bf=rc-bf=EH;
T=L_Rotate(T);
break;
case LH: //新结点插入在*T的右孩子的左子树上,要做双旋处理
ld=rc-lchild; //ld指向*T的右孩子的左子树根
switch(ld-bf){ //修改*T及其右孩子的平衡因子
case LH:
T-bf=EH;
rc-bf=RH;
break;
case EH:
T-bf=rc-bf=EH;
break;
case RH:
T-bf=LH;
rc-bf=EH;
break;
}///switch(ld-bf)
ld-bf=EH;
T-rchild=R_Rotate(T-rchild); //对*T的右孩子做右旋平衡处理
T=L_Rotate(T); //对*T做左旋处理
}/////switch(rc-bf)
return T;
}
int Delete(bstree T,int e){
//删除结点
bstree p,q;
e=0;
p=T;
if(!T-rchild) {//右子数为空需要重接它的左子数
T=T-lchild;
free(p);
shorter=true;
}
else if(!T-lchild) {//重接它的右子数
T=T-rchild;
free(p);
shorter=true;
}
else{ //左右子数均不空
q=T-lchild;
while(q-rchild!=NULL){//转左,然后向右到尽头
q=q-rchild;
}
e=q-data;
}
return e;
}
void Delete_Rightbalance(bstree T){
///////////删除在左子树上的,相当于插入在右子树
bstree rc=T-rchild,ld;
switch(rc-bf){
case LH://///////双旋 ,先右旋后左旋
ld=rc-lchild;
rc-lchild=ld-rchild;
ld-rchild=rc;
T-rchild=rc-lchild;
rc-lchild=T;
switch(ld-bf) {
case LH:T-bf=EH;
rc-bf=RH;
break;
case EH:T-bf=rc-bf=EH;
break;
case RH:T-bf=LH;
rc-bf=EH;
break;
}
ld-bf=EH;
T=rc;
shorter=true;break;
case EH:///////删除在左子树,相当于插入在右子树,左单旋
T-rchild=rc-lchild;
rc-lchild=T;
rc-bf=LH;
T-bf=RH;
T=rc;
shorter=EH;break;
case RH:///////删除在左子树,相当于插入在右子树,左单旋
T-rchild=rc-lchild;
rc-lchild=T;
rc-bf=T-bf=EH;
T=rc;
shorter=true;break;
}
}
void Delete_Leftbalance(bstree T)/////删除右子树上的,相当于插入在左子树上
{
bstree p1,p2;
p1=T-lchild;
switch(p1-bf) {
case LH:T-lchild=p1-rchild;//////右旋
p1-rchild=T;
p1-bf=T-bf=EH;
T=p1;
shorter=true;
break;
case EH:T-lchild=p1-rchild;///////右旋
p1-rchild=T;
p1-bf=RH;
T-bf=LH;
T=p1;
shorter=false;
break;
case RH:p2=p1-rchild;//////////右双旋
p1-rchild=p2-lchild;
p2-lchild=p1;
T-lchild=p2-rchild;
p2-rchild=T;
switch(p2-bf){
case LH:T-bf=RH;p1-bf=EH;break;
case EH:T-bf=EH;p1-bf=EH;break;
case RH:T-bf=EH;p1-bf=LH;break;
}
p2-bf=EH;
T=p2;
shorter=true;break;
}
}
3. 函数的调用关系图
Main
InsertAVL Preordertraverse FindAVL DeleteAVL
四、 调试分析
1. 在开始对平衡二叉树的插入后,再做平衡处理时,特别是在做双向旋转平衡处理后的更新时,费了一些时间;
2. 在做平衡二叉树的删除时,当删除结点左右孩子均在时,开始直接用左子树的最大数代替,然后直接删除结点,结果导致删除了将要删除的结点及其孩子均删除了,后来将要删除的结点用左子树的最大树代替后,对左子树的最大结点做好标记,然后再做对其做删除处理。
3. 本程序算法基本简单,没有多大困难,就是在分析做双旋平衡处理的更新时,开始思路有些混乱,后来就好了;
五、 用户手册
1. 本程序的运行环境为DOS操作系统,执行文件为Balanced Tree.exe。
2. 进入演示程序后,按广度遍历输入平衡二叉树,中间以回车键隔开,输入0为结束;再输入要插入的结点,输入0结束,再输入要查找的结点,最后可以输入要删除的结点,输入0结束
六、 测试结果
先按广度遍历创建平衡二叉树(亦可一个一个的插入二叉树的结点)(50 20 60 10 30 55 70 5 15 25 58 90) ,输入0结束,然后可插入结点(39),其会显示插入后的二叉树,输入0,不再插入;输入要查找结点(6),输入要删除的结点(20),其显示如下:
七、 附录
Balance Tree.cpp
递归的逻辑,简单来说就是要有一个切入点。从简单的数据逆推到复杂性的数据。