AVL树

平衡二叉树，是一个方便查找的树，树的左子树深度与右子树的深度的差总（BF）是在+1,0,-1之中。

随着树的建立，插入，树都会自动的进行调整，使得其满足上面的条件。

1、+1表示左子树的深度比右子树的深度多1.

2、0 表示左子树的深度与右子树的深度相同。

3、-1表示左子树的深度比右子树神的小1.

因此，如果一个数据插入到情况1中，也就是说，数据插入到左子树中，左子树的深度将会比右子树多2.此时，需要调整树的结构。如果插入尾端节点的左子树中，则这个尾端节点相应的BF值,就变成+1.相反，如果插入到它的右子树中，BF值就会变成-1.这个调整也会返回到上面一层的节点，再次进行调整。

 

这里相应的介绍一个左旋，与右旋的基本知识。

比如下图

在进行左旋时，将会发生下面的情况：

void L_Rotate(BiTree *p){
    //传入根节点进行右旋
    BiTree R;
    R = (*p)->rchild;
    (*p)->rchild = R->lchild;
    R->lchild = (*p);
    (*p) = R;
}

最后子树将会变成

 

相应的右旋，则运行下面的代码

void R_Rotate(BiTree *p){
    //传入一个根节点，进行右旋。定义它的左子树节点为L,根节点的左子树变成L的右子树，L的右子树变成根节点。最后把根节点指针指向L
    BiTree L;
    L = (*p)->lchild;
    (*p)->lchild =  L->rchild;
    L->rchild = (*p);
    (*p) = L;
}

 

了解左旋与右旋后，就该进行树的调整介绍了。

这里有一个技巧：

1 如果插入的元素插入到左子树，使得左子树的BF值发生改变。如果左子树节点的BF值，与根节点的BF值相同符号，则进行一次右旋，即可。但是如果是不同符号，则要进行双旋（即先进性左旋，使得子树高度加一，在进行右旋，平衡子树）

2 如果插入到右子树，也观察符号，相同，则进行一次右旋，如果不同，则进行双旋。

代码如下

void LeftBalance(BiTree *T){
    BiTree L,Lr;
    L = (*T)->lchild;
    switch(L->bf){
    case LH://符号与根相同，因此进行右旋一次，就行了
        (*T)->bf = L->bf = EH;
        R_Rotate(T);
        break;
    case RH://符号与根不同，要进行双旋；对子树进行一次旋转，再对T进行一次旋转
        Lr = L->rchild;
        switch(Lr->bf){
        case LH: //如果是左子数高，那么对根节点赋值为-1，因为没有右子树，根节点将会出现左子树为空的情况；左子树旋转后，会平衡为EH
            (*T)->bf = RH;
            L->bf = EH;
            break;
        case EH://如果为平衡，那么根节点和左子树节点都为平衡EH
            (*T)->bf = L->bf = EH;
            break;
        case RH://如果右子树高，那么对根节点赋值为0，对左子树赋值为+1，因为进行旋转后，左子树节点的右子树会空。根节点EH
            (*T)->bf = EH;
            L->bf = LH;
            break;
        }
        Lr->bf = EH;
        L_Rotate(&(*T)->lchild);
        R_Rotate(T);
    }
}

void RightBalance(BiTree *T){
    BiTree R,Rl;
    R = (*T)->rchild;
    switch(R->bf){
    case RH:
        (*T)->bf = R->bf = EH;
        L_Rotate(T);
        break;
    case LH:
        Rl = R->lchild;
        switch(Rl->bf){
        case LH: //如果是左子数高，那么对根节点赋值为-1，因为没有右子树，根节点将会出现左子树为空的情况；左子树旋转后，会平衡为EH
            (*T)->bf = EH;
            R->bf = RH;
            break;
        case EH://如果为平衡，那么根节点和左子树节点都为平衡EH
            (*T)->bf = R->bf = EH;
            break;
        case RH://如果右子树高，那么对根节点赋值为0，对左子树赋值为+1，因为进行旋转后，左子树节点的右子树会空。根节点EH
            (*T)->bf = LH;
            R->bf = EH;
            break;
        }
        Rl->bf = EH;
        R_Rotate(&(*T)->rchild);
        L_Rotate(T);
    }
}

插入时，要遍历到子树的最底层，进行分析，逐层的改变BF值，进行平衡。知道标记taller为0时，表示对深度不发生改变，就不需要向上遍历了。

int insertAVL(BiTree *T,int e, int *taller){
    if(!(*T)){
        (*T)=(BiTree)malloc(sizeof(BiTNode));
        (*T)->data = e;
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
        (*T)->bf = EH;
        *taller = 1;
    }else{
        if(e == (*T)->data){ //存在相同节点
            *taller = 0;
            return 0;
        }
        if(e < (*T)->data){
            if(!insertAVL(&(*T)->lchild,e,taller))
                return 0;
            if(taller){
                switch((*T)->bf){
                case LH:
                    LeftBalance(T);
                    *taller = 0;
                    break;
                case EH:
                    (*T)->bf = LH;
                    *taller = 1;
                    break;
                case RH:
                    (*T)->bf = EH;
                    *taller = 0;
                    break;
                }
            }
        }else{
            if(!insertAVL(&(*T)->rchild,e,taller))
                return 0;
            if(taller){
                switch((*T)->bf){
                case LH:
                    (*T)->bf = 0;
                    *taller = 0;
                    break;
                case EH:
                    (*T)->bf=RH;
                    *taller = 1;
                    break;
                case RH:
                    RightBalance(T);
                    *taller = 0;
                    break;
                }
            }
        }
    }
    return 1;
}

全部代码：

#include <stdio.h>
#include <stdlib.h>
#define LH +1
#define EH 0
#define RH -1

typedef struct BiTNode{
    int data;
    int bf;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void R_Rotate(BiTree *p);
void L_Rotate(BiTree *p);
void LeftBalance(BiTree *p);
void RightBalance(BiTree *T);
int insertAVL(BiTree *T,int e, int *taller);
void InOrderTree(BiTree b);

int main(){
    int i;
    int a[10]={4,7,9,1,2,3,0,5,6,8};
    BiTree T = NULL;
    int *taller = (int *)malloc(sizeof(int));
    for(i=0;i<10;i++){
        insertAVL(&T,a[i],taller);
        InOrderTree(T);
        printf("\n");
    }
    getchar();
}
void InOrderTree(BiTree b){
    if( b== NULL)
        return;
    InOrderTree(b->lchild);
    printf("%d ",b->data);
    InOrderTree(b->rchild);
}
int insertAVL(BiTree *T,int e, int *taller){
    if(!(*T)){
        (*T)=(BiTree)malloc(sizeof(BiTNode));
        (*T)->data = e;
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
        (*T)->bf = EH;
        *taller = 1;
    }else{
        if(e == (*T)->data){ //存在相同节点
            *taller = 0;
            return 0;
        }
        if(e < (*T)->data){
            if(!insertAVL(&(*T)->lchild,e,taller))
                return 0;
            if(taller){
                switch((*T)->bf){
                case LH:
                    LeftBalance(T);
                    *taller = 0;
                    break;
                case EH:
                    (*T)->bf = LH;
                    *taller = 1;
                    break;
                case RH:
                    (*T)->bf = EH;
                    *taller = 0;
                    break;
                }
            }
        }else{
            if(!insertAVL(&(*T)->rchild,e,taller))
                return 0;
            if(taller){
                switch((*T)->bf){
                case LH:
                    (*T)->bf = 0;
                    *taller = 0;
                    break;
                case EH:
                    (*T)->bf=RH;
                    *taller = 1;
                    break;
                case RH:
                    RightBalance(T);
                    *taller = 0;
                    break;
                }
            }
        }
    }
    return 1;
}

void R_Rotate(BiTree *p){
    //传入一个根节点，进行右旋。定义它的左子树节点为L,根节点的左子树变成L的右子树，L的右子树变成根节点。最后把根节点指针指向L
    BiTree L;
    L = (*p)->lchild;
    (*p)->lchild =  L->rchild;
    L->rchild = (*p);
    (*p) = L;
}
void L_Rotate(BiTree *p){
    //传入根节点进行右旋
    BiTree R;
    R = (*p)->rchild;
    (*p)->rchild = R->lchild;
    R->lchild = (*p);
    (*p) = R;
}
void LeftBalance(BiTree *T){
    BiTree L,Lr;
    L = (*T)->lchild;
    switch(L->bf){
    case LH://符号与根相同，因此进行右旋一次，就行了
        (*T)->bf = L->bf = EH;
        R_Rotate(T);
        break;
    case RH://符号与根不同，要进行双旋；对子树进行一次旋转，再对T进行一次旋转
        Lr = L->rchild;
        switch(Lr->bf){
        case LH: //如果是左子数高，那么对根节点赋值为-1，因为没有右子树，根节点将会出现左子树为空的情况；左子树旋转后，会平衡为EH
            (*T)->bf = RH;
            L->bf = EH;
            break;
        case EH://如果为平衡，那么根节点和左子树节点都为平衡EH
            (*T)->bf = L->bf = EH;
            break;
        case RH://如果右子树高，那么对根节点赋值为0，对左子树赋值为+1，因为进行旋转后，左子树节点的右子树会空。根节点EH
            (*T)->bf = EH;
            L->bf = LH;
            break;
        }
        Lr->bf = EH;
        L_Rotate(&(*T)->lchild);
        R_Rotate(T);
    }
}

void RightBalance(BiTree *T){
    BiTree R,Rl;
    R = (*T)->rchild;
    switch(R->bf){
    case RH:
        (*T)->bf = R->bf = EH;
        L_Rotate(T);
        break;
    case LH:
        Rl = R->lchild;
        switch(Rl->bf){
        case LH: //如果是左子数高，那么对根节点赋值为-1，因为没有右子树，根节点将会出现左子树为空的情况；左子树旋转后，会平衡为EH
            (*T)->bf = EH;
            R->bf = RH;
            break;
        case EH://如果为平衡，那么根节点和左子树节点都为平衡EH
            (*T)->bf = R->bf = EH;
            break;
        case RH://如果右子树高，那么对根节点赋值为0，对左子树赋值为+1，因为进行旋转后，左子树节点的右子树会空。根节点EH
            (*T)->bf = LH;
            R->bf = EH;
            break;
        }
        Rl->bf = EH;
        R_Rotate(&(*T)->rchild);
        L_Rotate(T);
    }
}

运行实例：

 

 

本文转自博客园xingoo的博客，原文链接：AVL树，如需转载请自行联系原博主。

时间： 2025-01-29 21:18:56

AVL树的相关文章

平衡二叉树:php实现平衡二叉树(avl树)

<?phprequire 'bstorder.php';$test = range(1, 10);//$test = array(3,9,1,4,8,5,7,6,2,10);$tree = new bst($test, true);//$tree->deletenode('30');(非平衡树可删除,平衡树的没写删除操作)print_r($tree->gettree());?>bstorder.php<?php/*** php实现二叉排序树* @author zhaojian

AVL树的实现代码

本文配套源码 /******************************************************************** created: 2007/08/28 filename: avltree.c author: Lichuang purpose: AVL树的实现代码, 参考资料<<数据结构与算法分析-C语言描述>>, 作者Allen Weiss **************************************************

二叉树学习笔记之经典平衡二叉树（AVL树）

二叉查找树(BSTree)中进行查找.插入和删除操作的时间复杂度都是O(h),其中h为树的高度.BST的高度直接影响到操作实现的性能,最坏情况下,二叉查找树会退化成一个单链表,比如插入的节点序列本身就有序,这时候性能会下降到O(n).可见在树的规模固定的前提下,BST的高度越低越好. 平衡二叉树 平衡二叉树是计算机科学中的一类改进的二叉查找树. 平衡二叉树具有以下性质: (1)一棵空树是平衡二叉树 (2)如果树不为空,它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树.

AVL树的研究

3 实现算法  3.1 数据结构 template<typename T>struct BSTNode//平衡二叉树的结点类型结构体 {        T data;//结点数据类型        int bf;//结点的平衡因子,比二叉链表结点多此项        BSTNode<T>*lchild,*rchild;//左右孩子指针 };   3.2 算法   3.2．1 递归法 递归实现AVL树的节点删除的思想如下.    在AVL树T上删除值为E的节点步骤如下: (1)   

AVL树的删除探讨

AVL树的删除很多教材上都没有提供,本人对AVL树有着较为深入的研究.现在晒出大体的算法思想.  3.2．1 递归法 递归实现AVL树的结点删除的思想如下.    在AVL树T上删除值为E的结点步骤如下: (1)       若树T为空,返回0退出否则到(2); (2)       比较T的数据和E,若相等跳到(3),若E小于T->data跳到(4),若E大于T->data则跳到(5) (3)       分析T结点的类型 (3.1)若T是叶子结点则直接删除,树变矮即lower=1: (3.2

Python数据结构——AVL树的实现

既然,我们已经证明,保持 AVL 树的平衡将会使性能得到很大的提升,那我们看看如何在程序中向树插入一个新的键值.因为所有的新键是作为叶节点插入树的,而新叶子的平衡因子为零,所以我们对新插入的节点不作调整.不过一旦有新叶子的插入我们必须更新其父节点的平衡因子.新叶子会如何影响父节点的平衡因子取决于叶节点是左子节点还是右子节点.如果新节点是右子节点,父节点的平衡因子减 1.如果新节点是左子节点,父节点的平衡因子将加 1.这种关系可以递归地应用于新节点的前两个节点,并有可能影响到之前的每一个甚至是根节

纸上谈兵: AVL树[转]

二叉搜索树的深度与搜索效率 我们在树, 二叉树, 二叉搜索树中提到,一个有n个节点的二叉树,它的最小深度为log(n),最大深度为n.比如下面两个二叉树: 深度为n的二叉树 深度为log(n)的二叉树 这两个二叉树同时也是二叉搜索树(参考树, 二叉树, 二叉搜索树).注意,log以2为基底.log(n)是指深度的量级.根据我们对深度的定义,精确的最小深度为floor(log(n)+1). 我们将处于同一深度的节点归为一层.如果除最后一层外的其他层都被节点填满时,二叉树有最小深度log(n). 二

AVL树双旋转疑问

问题描述 近日在学习AVL树的旋转,尤其是双旋转处有些模糊不清,在MarkAllenWeiss的数据结构与算法分析--C语言描述这本书里面看到,感觉书中的双旋转例程有错误,如下图:这里面的代码显示先右旋,然后左旋,可是注释里面写着是Left-right双旋转,难道不是先左旋,后右旋吗?好像先左旋,后右旋才是正确的做法.请各位指点一下!谢谢.

AVL树删除算法的实现--长安大学毕业设计

AVL树的删除算法的两种实现方法 本文是本人原创,当时作为长安大学高一凡老师带的学生,我的毕业设计就是做一个AVL 算法的演示软件.其中,AVL树的删除算法在度娘和 谷歌了很久都没有找到逻辑通畅或者说是我能够看懂的.后来,闭门造成,费了十几张A4纸才把算法设计出来.实现之后得到了老师的认同.非常的开心.之前我骗了大家,用网络上能搜到的算法来敷衍大家,一直觉得我的努力成果,不能让别人剽窃.但是,这么多年过去了.我觉得,我要和CSDN上其他码农一样,需要具有分享精神.... 本文是当时我想投稿的一个

数据结构之AVL树

树的平衡,我们已经知道DWL算法,不过DWL算法需要从整体上平衡树,但是树的平衡也可以局部的进行,由Adel'son-Vel'skii-Landis提出了一种经典方法,称为AVL树. 1.概念:AVL树,或者说可适应树,是指树中每个节点的的平衡因子的绝对值不大于1,即只能为-1,0,1 平衡因子:节点的右子树的高度减去左子树的高度 2.AVL树的插入:从新插入节点到根的路径上,修改遇到的节点的平衡因子即可,对其他部分没影响 1)向右子女的右子树插入一个节点,单旋转就可以 2)向右子女的左子树插入