6.平衡二叉查找树

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)

现有一棵无重复关键字的平衡二叉树（AVL 树）

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

AVL树所有的java递归算法

递归的逻辑，简单来说就是要有一个切入点。从简单的数据逆推到复杂性的数据。

文章名称：avl平衡树java代码,avl树java实现
文章URL：http://chengdu.cdxwcx.cn/article/dsepjdh.html