时间戳

首页 > 技术文章 > AVL平衡二叉树实现，图解分析，C++描述，完整可执行代码

AVL平衡二叉树实现，图解分析，C++描述，完整可执行代码

meihao1203 2018-07-05 17:16 原文

算法完整可运行代码地址：https://github.com/meihao1203/learning/tree/master/07052018/AVL_%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91
平衡二叉树(AVL树):  G.M. Adelson-Velsky和E.M. Landis
  平衡二叉树（Height-Balanced Binary Search Tree 或 Self-Balancing Binary Search Tree），一种高度平衡的二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

平衡因子BF(Balance Factor):
  将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子。AVL树上的平衡因子只可能是-1、0和1。

//图1不是平衡二叉树
距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。
右图：当新插入结点37时，距离它最近的平衡因子绝对值超过1的结点是58（即它的左子树高度2减去右子树高度0），所以从58开始以下的子树为最小不平衡子树。

平衡二叉树实现原理：
  平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
{3,2,1,4,5,6,7,10,9,8}

当最小不平衡子树根结点的平衡因子BF是大于1是，右旋。顺时针
最小不平衡子树根结点的平衡因子BF是小于-1是，左旋。逆时针
最小不平衡子树的BF与它的子树的BF符号相反时，对应它的子树符号先旋转子树，再最小不平衡子树旋转。 		 
2,1 R右旋转
    -2 -1 L左旋转     
        // 7的BF=-2,10的BF=1; 右平衡旋转
  // 先右旋10，在左旋7           
  // 出现6BF=-2,9BF=1; 右平衡旋转     


当根结点为空，结点高度height=0,一个结点=1,根结点高度等价树的层数
//介绍算法中用到的几个旋转操作方法

左子树插入元素导致左子树不平衡，右旋转

右图，这是最复杂的情况，其他情况都是一样的，插入一个结点采用递归算法在二叉树的叶子结点的合适位置插入，函数最后准备返回的时候回更新刚才插入的数据的高度，递归层层返回后第一件事就是判断当前结点左右子树的高度差；

1更新高度为1，返回 BF=0
2更新高度为2，返回 BF=1 返回
3更新高度为3，返回 BF=1 返回
4更新高度为4，返回 BF=2 不平衡，旋转调整，2 1所以采用右旋
转
pavlNode LL_Right_Rotate(pavlNode& root)
{
        if(nullptr==root)
                return nullptr;
        //定义一个指针指向root的左子树
        AvlNode* left = root->lchild;
        root->lchild = left->rchild;
        left->rchild = root;
        //此时根结点变为left
        //调整树的每个结点的高度

        root->height = max(AvlTreeHeight(root->lchild),AvlTreeHeight(root->rchild)) + 1;  //加一是自身节点
        left->height = max(AvlTreeHeight(left->lchild),root->height) + 1;

        return left;  //新的根结点
}
    
右子树插入元素导致右子树不平衡，坐旋转
-2 -1所以采用左旋转，逆时针
pavlNode RR_Left_Rotate(pavlNode& root)
{
        if(nullptr==root)
                return nullptr;
        AvlNode* right = root->rchild;
        root->rchild = right->lchild;
        right->lchild = root;

        root->height = max(AvlTreeHeight(root->lchild),AvlTreeHeight(root->rchild)) + 1;
        right->height = max(AvlTreeHeight(right->rchild),root->height) + 1;

        return right;
}
    
左子树的右子树插入导致不平衡  左平衡旋转LR
2 -1 LR,左平衡旋转  先对结点为2的子树左旋转，后对结点5的子树右旋转

pavlNode LR_Left_Right_Rotate(pavlNode& root)
{
        root->lchild = RR_Left_Rotate(root->lchild);  
//获得旋转后的根结点，前面一定要补货最后旋转玩后的root->lchild
        return LL_Right_Rotate(root);
}
    
右子树的左子树插入导致不平衡  右平衡旋转RL
-2 1 RL,右平衡旋转  先对结点5的子树进行右旋转，后对结点2的子树左旋转

pavlNode RL_Right_Left_Rotate(pavlNode& root)
{
        root->rchild = LL_Right_Rotate(root->rchild);
        return RR_Left_Rotate(root);
}
            



{3,2,1,4,5,6,7,10,9,8}建立好AVL树后按插入次序依次删除
删除3 删除2 不平衡，右子树高度减左子树高度2，调整，右子树(根结点7)的左右子树相同，-2,0 RR
删除1 不平衡 -2,1 RL 删除4
删除5 删除6 不平衡，-2,0 RR
删除7 删除10 删除9        删除8 null


//源代码,参考博客：https://www.cnblogs.com/skywang12345/p/3576969.html
/* AVL.h */
#ifndef __AVL_H__
#define __AVL_H__
#include<iostream>
using namespace std;
typedef struct AVLTreeNode
{
        int key;
        int height;  //结点高度，用来计算当前结点为根结点的子树是不是平衡的
        struct AVLTreeNode* lchild;
        struct AVLTreeNode* rchild;
}AvlNode,*pavlNode;
//height,当根结点为空，height=0,一个结点=1,根结点等价数的层数

int AvlTreeHeight(AvlNode* root)
{
        return (nullptr==root)? 0 : (root->height);
}
//求最大值
int max(int a,int b)
{
        return a>b?a:b;
}
//LL 左子树插入或删除结点导致左子树不平衡，要右旋转，返回旋转调整后的树根结点
pavlNode LL_Right_Rotate(pavlNode& root)
{
        if(nullptr==root)
                return nullptr;
        //定义一个指针指向root的左子树
        AvlNode* left = root->lchild;
        root->lchild = left->rchild;
        left->rchild = root;
        //此时根结点变为left
        //调整树的每个结点的高度

        root->height = max(AvlTreeHeight(root->lchild),AvlTreeHeight(root->rchild)) + 1;  //加一是自身节点
        left->height = max(AvlTreeHeight(left->lchild),root->height) + 1;

        return left;  //新的根结点
}
//RR 右子树插入或删除结点导致右子树不平衡，要左旋转，返回调整后的树根结点
pavlNode RR_Left_Rotate(pavlNode& root)
{
        if(nullptr==root)
                return nullptr;
        AvlNode* right = root->rchild;
        root->rchild = right->lchild;
        right->lchild = root;

        root->height = max(AvlTreeHeight(root->lchild),AvlTreeHeight(root->rchild)) + 1;
        right->height = max(AvlTreeHeight(right->rchild),root->height) + 1;

        return right;
}
//LR 左子树的右子树插入或删除结点导致不平衡，也就是左子树和左子树的右子树平衡因子一正一负
//先左子树的右子树左旋转，然后左子树右旋转
pavlNode LR_Left_Right_Rotate(pavlNode& root)
{
        root->lchild = RR_Left_Rotate(root->lchild);  //获得旋转后的根结点，前面一定要补货最后旋转玩后的root->lchild
        return LL_Right_Rotate(root);
}
//RL 右子树的左子树插入或删除结点导致不平衡，也就是右子树和右子树的左子树平衡因子一负一正
//先右子树的左子树右旋转，然后右子树坐旋转
pavlNode RL_Right_Left_Rotate(pavlNode& root)
{
        root->rchild = LL_Right_Rotate(root->rchild);
        return RR_Left_Rotate(root);
}

//AVL树插入一个结点
//思路：如果树为空，直接插入，最后计算树的高度并返回根结点地址
//不空，采用递归，新结点只能插入到树的最后，插入完后计算新结点的高度，
//递归层层返回，每返回一层就计算当前根结点的左右子树高度差，也就是上一次递归返回的时候就算的，发现不平衡（高度>1）
//说明从当前结点开始的子树即不平衡了，立即旋转调整，判断是在当前子树的左边还是右边插入的，采取合适的旋转策略
pavlNode AvlTreeInsertNode(pavlNode& root,int key)
{
        if(nullptr==root)
        {
                root = new AvlNode();
                if(nullptr==root)
                {
                        cout<<"new 开辟AvlNode空间失败"<<endl;
                        return nullptr;
                }
                root->height = 0;  //初始为0，函数最后会计算更新
                root->key = key;
                root->lchild = root->rchild = nullptr;
        }
        else if(key<root->key)  //比根结点小，左子树寻找
        {
                root->lchild = AvlTreeInsertNode(root->lchild,key);  //递归寻找
                //递归返回，判断子树还是不是平衡的了
                //因为只在左子树插入的，只会增加左子树的高度,对右子树没有影响
                if(2 == AvlTreeHeight(root->lchild) - AvlTreeHeight(root->rchild))  //模拟递归的层层嵌套，从在叶子结点插入新结点的位置回溯，这里不用加取绝对值运算的，不会出现负数
                {
                        //LL，左子树的左子树插入引起不平衡  BF 2 1 LL
                        if(key<root->lchild->key)
                                root = LL_Right_Rotate(root);  //旋转调整，返回新的根结点
                        else  //BF 2 -1  没有Bf 2 0的情况
                                root = LR_Left_Right_Rotate(root); 
                }
        }
        else if(key>root->key)  //大于根结点，在右子树插入
        {
                root->rchild = AvlTreeInsertNode(root->rchild,key);
                if(2==AvlTreeHeight(root->rchild) - AvlTreeHeight(root->lchild))
                {
                        //RR BF -2 -1
                        if(key>root->rchild->key)
                                root = RR_Left_Rotate(root);
                        else //RL BF -2 1
                                root = RL_Right_Left_Rotate(root);
                }
        }
        else if(key==root->key)
        {  //如果AVL树运行两个相等的元素，这里不要就好了，前面>=
                cout<<"该关键字存在，禁止插入"<<endl;
                return root;
        }
        root->height = max(AvlTreeHeight(root->lchild),AvlTreeHeight(root->rchild)) + 1;  //最后这里才能计算更新height,因为递归返回的时候回旋转跳转子树
        return root;
}


//思路：和插入操作一样，递归寻找要删除的结点，
//如果关键字有左右子树，根据左右子树的高度，选择高度高的一遍的相应结点替换要删除的关键字，
//比如左子树高，就选左子树的最右结点，也就是关键字的前驱
//右子树高，就选右子树的最左结点，也就是关键字的后继
//替换之后再在对应的子树里面删除刚用来替换的结点
//如果左右子树不是存在，则选择不为空的一个直接替换
//删除完最后还要更新高度
static enum errorFlag{delFalse=0,delTrue} AvlTreeDeleteNodeErrorFlag;
pavlNode AvlTreeDeleteNode(pavlNode& root,int key)
{
        AvlTreeDeleteNodeErrorFlag = delFalse;
        if(nullptr==root)
        {
                AvlTreeDeleteNodeErrorFlag = delTrue;  //如果是最后一个结点删除，也会返回nullptr，所以加一个错误标志
                return nullptr;
        }
        if(key<root->key)
        {
                root->lchild = AvlTreeDeleteNode(root->lchild,key);
                //如果左子树删除导不平衡,左子树删除可能导致和右子树不平衡
                //如果不平衡，是右子树的右子树太高导致的还是右子树的左子树左子树导致的
                if(2==AvlTreeHeight(root->rchild) - AvlTreeHeight(root->lchild))
                {//在左子树删掉的，只能右子树高于左子树2
                //动态调整root->rchild
                //判断右子树的左右子树高度，决定是RL还是RR
                        if( AvlTreeHeight(root->rchild->lchild) <= AvlTreeHeight(root->rchild->rchild) )
                        {//RR,右边高->平衡因子负 先左旋转 root=-2,root->rchild->lchild = -1  一负负，RR_Left_Rotate  或者BF -2 0
                                root = RR_Left_Rotate(root); 
                        }
                        else
                        {//RL  root=-2,root->rchild->lchild = 1  只有这种情况才是RL
                                root = RL_Right_Left_Rotate(root);
                        }
                }
        }
        else if(key>root->key)
        {
                root->rchild = AvlTreeDeleteNode(root->rchild,key);
                if(2==AvlTreeHeight(root->lchild) - AvlTreeHeight(root->rchild))
                {
                        if( AvlTreeHeight(root->lchild->lchild) >= AvlTreeHeight(root->lchild->rchild) )
                        {//LL  BF 2 1 BF 2 0
                                root = LL_Right_Rotate(root);
                        }
                        else
                        {//LR  BF 2 -1
                                root = LR_Left_Right_Rotate(root);
                        }
                }
        }
        else if(key==root->key)
        {//找到，删除
                if(root->lchild!=nullptr && root->rchild!=nullptr)
                {//左右子树都不空，只能选当前结点的前驱或者后继来替换，然后删了这个前驱或后继
                //为了保持平衡，一般选当前要删除结点的左右子树中较高的一方
                        if(AvlTreeHeight(root->lchild) > AvlTreeHeight(root->rchild))
                        {//左子树中找前驱
                                AvlNode* delNode = AvlTreeNodePre(root->lchild,key);
                                root->key = delNode->key;  //修改替换数值
                                //左子树中删除delNode
                                root->lchild = AvlTreeDeleteNode(root->lchild,delNode->key);
                        }
                        else
                        {
                                AvlNode* delNode = AvlTreeNodePost(root->rchild,key);
                                root->key = delNode->key;
                                root->rchild = AvlTreeDeleteNode(root->rchild,delNode->key);
                        }
                }
                else //删除结点至少有一边没有孩子
                {
                        AvlNode* tmp = root;
                        root = nullptr==root->lchild ? root->rchild : root->lchild;
                        delete tmp;
                        tmp = nullptr;
                }
        }
        //更新结点高度
        if(nullptr!=root) //删除只有一个结点的特殊情况
        {
                root->height = ( max( AvlTreeHeight(root->lchild) , AvlTreeHeight(root->rchild) ) ) + 1;
        }
        return root;
}

AvlNode* AvlTreeNodePre(pavlNode root,int key)
{
        if(nullptr==root)
                return nullptr;
        while(nullptr!=root->rchild)
                root = root->rchild;
        return root;
}
AvlNode* AvlTreeNodePost(pavlNode root,int key)
{
        if(nullptr==root)
                return nullptr;
        while(nullptr!=root->lchild)
                root = root->lchild;
        return root;
}
void preorderTraversalAVL(const pavlNode& root)
{
        if(nullptr==root)
                return ;
        cout<<root->key<<"（"<<root->height<<"）"<<" ";
        preorderTraversalAVL(root->lchild);
        preorderTraversalAVL(root->rchild);
}
void inorderTraversalAVL(const pavlNode& root)
{
        if(nullptr==root)
                return ;
        inorderTraversalAVL(root->lchild);
        cout<<root->key<<"（"<<root->height<<"）"<<" ";
        inorderTraversalAVL(root->rchild);
}

void AvlTreeDestroy(pavlNode& root)
{
        if(nullptr==root)
                return ;
        if(nullptr!=root->lchild)
                AvlTreeDestroy(root->lchild);
        if(nullptr!=root->rchild)
                AvlTreeDestroy(root->rchild);
        delete root;
        root = nullptr;
}
#endif

/* AVL.h */
#ifndef __AVL_H__
#define __AVL_H__

typedef struct AVLTreeNode
{
        int key;
        int height;  //结点高度，用来计算当前结点为根结点的子树是不是平衡的
        struct AVLTreeNode* lchild;
        struct AVLTreeNode* rchild;
}AvlNode,*pavlNode;

//height,当根结点为空，height=0,一个结点=1,根结点等价数的层数
int AvlTreeHeight(AvlNode* root);

//求最大值
int max(int a,int b);

pavlNode LL_Right_Rotate(pavlNode& root);

pavlNode LR_Left_Right_Rotate(pavlNode& root);

pavlNode RL_Right_Left_Rotate(pavlNode& root);

pavlNode AvlTreeInsertNode(pavlNode& root,int key);

AvlNode* AvlTreeNodePre(pavlNode root,int key);  //找子树前驱，也就是最右结点，最大值结点

AvlNode* AvlTreeNodePost(pavlNode root,int key);  //找子树后继，也就是最左结点，最小值结点

static enum errorFlag{delFalse=0,delTrue} AvlTreeDeleteNodeErrorFlag;
pavlNode AvlTreeDeleteNode(pavlNode& root,int key);

AvlNode* AvlTreeNodePre(pavlNode root,int key);

AvlNode* AvlTreeNodePost(pavlNode root,int key);

void preorderTraversalAVL(const pavlNode& root);

void inorderTraversalAVL(const pavlNode& root);

void AvlTreeDestroy(pavlNode& root);
#endif


/* testmain.h */
#include"AVL.h"
#include<iostream>
using namespace std;
#define len 10
int main()
{
        //int a[len] = {3,2,1,4,5,6,7,10,9,8};
        int a[len] = {62,88,58,47,35,73,51,99,37,93};
        cout<<"待插入元素序列：";
        for(int idx=0;idx!=len;++idx)
        {
                cout<<a[idx]<<" ";
        }
        cout<<endl;


        pavlNode root = nullptr;
        for(int idx=0;idx!=len;++idx)
        {
                root = AvlTreeInsertNode(root,a[idx]);  //因为在插入过程中会修改根结点
                if( nullptr == root )
                        cout<<"insert "<<a[idx]<<" fail!"<<endl;
        }
        cout<<"中序遍历：";
        inorderTraversalAVL(root);
        cout<<endl;
        cout<<"后序遍历：";
        preorderTraversalAVL(root);
        cout<<endl<<endl;

        for(int idx=0;idx!=len;++idx)
        {
                if( nullptr == AvlTreeDeleteNode(root,a[idx]) && delTrue ==AvlTreeDeleteNodeErrorFlag )
                        cout<<"delete "<<a[idx]<<" fail!"<<endl;
                else
                {
                        cout<<"删除"<<a[idx]<<",中序遍历：";
                        inorderTraversalAVL(root);
                        cout<<endl;
                        cout<<"删除"<<a[idx]<<",后序遍历：";
                        preorderTraversalAVL(root);
                        cout<<endl<<endl;
                }
        }
        system("pause");
}


//待插入元素序列：3 2 1 4 5 6 7 10 9 8
//中序遍历：1（1） 2（2） 3（1） 4（4） 5（1） 6（2） 7（3） 8（1） 9（2） 10（1）
//后序遍历：4（4） 2（2） 1（1） 3（1） 7（3） 6（2） 5（1） 9（2） 8（1） 10（1）
//
//删除3,中序遍历：1（1） 2（2） 4（4） 5（1） 6（2） 7（3） 8（1） 9（2） 10（1）
//删除3,后序遍历：4（4） 2（2） 1（1） 7（3） 6（2） 5（1） 9（2） 8（1） 10（1）
//
//删除2,中序遍历：1（1） 4（3） 5（1） 6（2） 7（4） 8（1） 9（2） 10（1）
//删除2,后序遍历：7（4） 4（3） 1（1） 6（2） 5（1） 9（2） 8（1） 10（1）
//
//删除1,中序遍历：4（1） 5（2） 6（1） 7（3） 8（1） 9（2） 10（1）
//删除1,后序遍历：7（3） 5（2） 4（1） 6（1） 9（2） 8（1） 10（1）
//
//删除4,中序遍历：5（2） 6（1） 7（3） 8（1） 9（2） 10（1）
//删除4,后序遍历：7（3） 5（2） 6（1） 9（2） 8（1） 10（1）
//
//删除5,中序遍历：6（1） 7（3） 8（1） 9（2） 10（1）
//删除5,后序遍历：7（3） 6（1） 9（2） 8（1） 10（1）
//
//删除6,中序遍历：7（2） 8（1） 9（3） 10（1）
//删除6,后序遍历：9（3） 7（2） 8（1） 10（1）
//
//删除7,中序遍历：8（1） 9（2） 10（1）
//删除7,后序遍历：9（2） 8（1） 10（1）
//
//删除10,中序遍历：8（1） 9（2）
//删除10,后序遍历：9（2） 8（1）
//
//删除9,中序遍历：8（1）
//删除9,后序遍历：8（1）
//
//删除8,中序遍历：
//删除8,后序遍历：
//
//请按任意键继续. . .
//
//待插入元素序列：62 88 58 47 35 73 51 99 37 93
//中序遍历：35（2） 37（1） 47（3） 51（1） 58（2） 62（4） 73（1） 88（3） 93（1） 99（2）
//后序遍历：62（4） 47（3） 35（2） 37（1） 58（2） 51（1） 88（3） 73（1） 99（2） 93（1）
//
//删除62,中序遍历：35（2） 37（1） 47（3） 51（1） 58（2） 73（4） 88（1） 93（2） 99（1）
//删除62,后序遍历：73（4） 47（3） 35（2） 37（1） 58（2） 51（1） 93（2） 88（1） 99（1）
//
//删除88,中序遍历：35（2） 37（1） 47（3） 51（1） 58（2） 73（4） 93（2） 99（1）
//删除88,后序遍历：73（4） 47（3） 35（2） 37（1） 58（2） 51（1） 93（2） 99（1）
//
//删除58,中序遍历：35（2） 37（1） 47（3） 51（1） 73（4） 93（2） 99（1）
//删除58,后序遍历：73（4） 47（3） 35（2） 37（1） 51（1） 93（2） 99（1）
//
//删除47,中序遍历：35（1） 37（2） 51（1） 73（3） 93（2） 99（1）
//删除47,后序遍历：73（3） 37（2） 35（1） 51（1） 93（2） 99（1）
//
//删除35,中序遍历：37（2） 51（1） 73（3） 93（2） 99（1）
//删除35,后序遍历：73（3） 37（2） 51（1） 93（2） 99（1）
//
//删除73,中序遍历：37（2） 51（1） 93（3） 99（1）
//删除73,后序遍历：93（3） 37（2） 51（1） 99（1）
//
//删除51,中序遍历：37（1） 93（2） 99（1）
//删除51,后序遍历：93（2） 37（1） 99（1）
//
//删除99,中序遍历：37（1） 93（2）
//删除99,后序遍历：93（2） 37（1）
//
//删除37,中序遍历：93（1）
//删除37,后序遍历：93（1）
//
//删除93,中序遍历：
//删除93,后序遍历：
//
//请按任意键继续. . .



推荐阅读