平衡二叉树概念

平衡二叉排序树（Balanced Binary Tree），因由前苏联数学家Adelson-Velskii 和
Landis于1962年首先提出的，所以又称为AVL树。

平衡二叉树是一种特殊的二叉排序树，理解平衡二叉树首先要理解什么是二叉排序树。
如果已经了解二叉排序树可以直接看下面平衡二叉树内容。

二叉排序树（Binary Sort Tree）

所谓二叉排序树(BST)即：
（1）若该树的左子树不为空，那么左子树所有结点的值均小于其根结点的值。
（2）若该树的右子树不为空，那么右子树所有结点的值均大于其根结点的值。
（3）该树的左右子树也均为二叉排序树。
依此定义，我们可以通过比较根结点的值一层层地定位到所要查找的值。

例：如下图是一棵二叉排序树

比如我们要查找7，那么先从根结点开始比较，8>7查找左子树 ----> 3<7查找右子树 ----> 6>7查找右子树 ----> 最后7=7，找到了7。
这种查找算法与折半查找相似，也是逐步缩小搜索范围。
若中序遍历上图，则可以得到一个按数值大小排序的递增序列：1，3，4，6，7，8，10，13，15。

二叉排序树的储存结构

typedef struct BSTNode
{
	int data=0;//数据项
	struct BSTNode *lchild=NULL,*rchild=NULL;//左右子树
}BSTNode,*BSTree.

二叉排序树的查找算法（递归查找）

BSTree T 为二叉树根节点 ，int e 为查找的关键字。时间复制度为O(log2 n)。

int searchTree(BSTree T,int e)//在二叉树中查找给定关键字(函数返回值为成功1,失败0)
{
    if (T==NULL)//无法查找到给定关键字
    {
        return 0;
    }else if (e==T->data)//查找到关键字
    {
        return 1;
    }else if (e<T->data)//小于根结点，向左子树查找
    {
        return searchTree(T->lchild,e);
    }else if(e>T->data)//大于根结点，向右子树查找
    {
        return searchTree(T->rchild,e);
    }
}

二叉排序树的创建及插入（递归）

二叉排序树的插入算法基本过程也是查找，时间复制度也为O(log2 n)。

void InsertBST(BSTree &T,int e)//插入节点，根据节点值的大小插入
{//当二叉排序树中不存在关键字等于e的结点时，查找结束，插入结点
    if (!T)//查找到插入位置
    {
        BSTNode *S; //生成新结点
        S=new BSTNode;
        S->data=e;//给新结点赋值
        S->lchild=S->rchild=NULL;//将新结点作为叶子结点
        T=S;//给查找到的插入位置赋值
    }
    else if (e<T->data)
    {
        InsertBST(T->lchild,e);//向左查找插入
    }else if (e>T->data)
    {
        InsertBST(T->rchild,e);//向右查找插入
    }
}
void CreatBST(BSTree &T)//创建二叉树
{
    T=NULL;
    int e,n,i;
    scanf("%d",&n);
    for (i=0;i<n;i++)
    {
        scanf("%d",&e);
        InsertBST(T,e);
    }
}

平衡二叉树

介绍完二叉排序树，我们就来看看平衡二叉树。
平衡二叉树就是在二叉排序树上建立的，可以说是具有以下两个特征的二叉排序树：
（1）左子树和右子树的深度之差的绝对值不超过1。
（2）左子树和右子树也是平衡二叉树。

平衡因子

为了方便记录和计算左右子树深度之差，我们引入一个概念叫平衡因子。
平衡因子就是该结点左右子树深度之差，由平衡二叉树的定义我们可以知道平衡二叉树上的平衡因子只可能是-1，0，1 。

二叉排序树的储存结构

typedef struct AVLNode
{
    int data=0;//结点值
    int depth=0;//深度，方便通过计算左右子树深度之差得到该结点的平衡因子
    struct AVLNode *father=NULL;//父结点
    struct AVLNode *lchild=NULL,*rchild=NULL;//左右结点
} AVLNode,*AVLTree; //结点结构体

计算平衡因子代码实现：

int count_depth(AVLTree &T)//计算各结点的深度
{
    if(T==NULL)
    {
        return 0;
    }
    else
    {
        int l=count_depth(T->lchild);//左子树深度
        int r=count_depth(T->rchild);//右子树深度
        return T->depth=max(l,r)+1;//更新深度
    }
}

int get_balance(AVLTree T)//读取深度
{
    if(T)
    {
        return T->depth;
    }
    else
    {
        return 0;
    }
}

int count_balance(AVLTree T)//计算平衡因子
{
    if(!T)
    {
        return 0;
    }
    else
    {
        return get_balance(T->lchild)-get_balance(T->rchild);//平衡因子等于左右子树的深度之差
    }
}

平衡二叉树的创建及调整方法

如何创建一棵平衡二叉树呢？
简单的来说就是：
（1）先按照我们创建二叉排序树的方法，找到结点插入位置，将结点插入二叉树中。

（2）然后我们来计算该插入结点父结点的平衡因子， 如果平衡因子绝对值大于1，代表该子树是不平衡的，那么对该子树进行调整，将其调整为平衡二叉树， 然后一层一层往上计算平衡因子和进行调整，直到根节点（根结点平衡因子绝对值大于1也要调整），最终把整棵树调整为平衡二叉树。

（3）第三步就重复上面操作，把一个一个结点插入二叉树中并进行调整，最终插入完所有结点并创建完成平衡二叉树。

平衡二叉树的调整

平衡二叉树的调整有4种调整情况。

这里有一篇写得比较好的文章可以参考一下：平衡二叉树（AVL）图解与实现-zthgreat

LL型

(a) 图a中我们插入“16” 后计算平衡因子发现结点“31”的平衡因子为2，该树为非平衡树，需要进行调整，我们以结点“25”为旋转中心，将其父结点按顺时针旋转为其右子树，至此该树调整完毕。
注意：25的左结点16不进行旋转。
(b) 图b中我们插入“9”后计算平衡因子发现结点“31”的平衡因子为2，该树为非平衡树，需要进行调整，我们以结点“25”为旋转中心，将其父结点“31”按顺时针旋转为其右子树，再把旋转中心“25”的右子树调整为31的左子树，至此该树调整完毕。

?? 我们总结出以下规律（参考下图）：将B结点作为根结点，A结点旋转为B结点的右子树，再把B结点本来的右子树连接为A结点的左子树，该树调整完成。

代码实现：

AVLTree L