AVL树是带有平衡的二叉查找树！一颗AVL树的每一个结点的左子树和右子树的深度最多只有1的差距，这就保持了这颗二叉树的平衡！很大程度的提高了树的使用效率！

当我们对树进行一系列操作（插入、删除等）后，AVL树很可能就不能保持AVL的特性，所以在进行操作时，我们必须重新平衡这颗二叉树！

我们把必须重新平衡的结点叫做α（这样可以减少很多文字，又好理解），由于任意结点最多只有两个儿子，因此出现高度不平衡就需要α点的两个子结点高度差大于等于2。

如意看出，这种不平衡可能出现下面四种情况：

1、对α的左子树的左子树进行插入；

2、对α的左子树的右子树进行插入；

3、对α的右子树的右子树进行插入；

4、对α的右子树的左孩子进行插入。

1、3的情况是比较简单的，进行一次旋转就能完成平衡，而2、4的情况就比较复杂了，需要两次旋转！

我先定义一个AVL数的结点结构，只比查找树多一个属性：深度

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*结点数据域类型定义*/
typedef int ElemType;

/*AVL树的结点声明*/
typedef struct _AVLTNode
{
		ElemType data;
		struct _AVLTNode * lchild;
		struct _AVLTNode * rchild;
		int height;		/*深度*/
}AVLTNode,*AVLTree;

还需要一个辅助的函数，帮助获取这个深度

/*获取树的高度*/
static int Height(AVLTree T)
{
	if(!T)
	{
		return -1;
	}
	else
	{
		return T->height;
	}
}

/*AVL书中插入结点，插入完毕后树依然保持AVL特性*/
AVLTree AVL_Insert(AVLTree * T, ElemType e)
{
	if (*T == NULL)			//如果空树，就构造一颗根结点
	{
		*T = (AVLTree)malloc(sizeof(AVLTNode));
		if(!*T)
		{
			return NULL;
		}

		(*T)->data = e;
		(*T)->lchild = NULL;
		(*T)->rchild = NULL;
		(*T)->height = 0;		//初始化深度为0；
	} 
	else if(e < (*T)->data)			//左边
	{
		(*T)->lchild =AVL_Insert(&(*T)->lchild,e);			//递归左子树插入

		if (Height((*T)->lchild) - Height((*T)->rchild) == 2)			//判断左子树和右子树的深度差为2 说明AVL特性被破坏，需要进行平衡
		{
			if (e < (*T)->lchild->data)				//属于 上面四种情况中的第一个，只需要一次旋转
			{
				*T = SingleRotateLeft(*T);
			} 
			else
			{
				*T = DoubleRotateLeft(*T);		//第二个情况 双旋转
			}
		}
	}
	else if(e > (*T)->data)			//反之 右面，操作和左面相反而已
	{
		(*T)->rchild =AVL_Insert(&(*T)->rchild,e);
		if (Height((*T)->rchild) - Height((*T)->lchild) == 2)
		{
			if (e > (*T)->rchild->data)
			{
				*T = SingleRotateRight(*T);
			}
			else
			{
				*T = DoubleRotateRight(*T);
			}
		}
	}

	(*T)->height = Max(Height((*T)->rchild),Height((*T)->lchild))+1;		//深度加1
	return *T;
}

/*AVL树左单旋转*/
static AVLTree SingleRotateLeft(AVLTree k1)
{
	AVLTree k2;

	k2 = k1->lchild;
	k1->lchild = k2->rchild;
	k2->rchild = k1;

	k1->height =  Max(Height(k1->rchild),Height(k1->lchild))+1;
	k2->height =  Max(Height(k2->rchild),Height(k2->lchild))+1;
	return k2;
}

/*AVL树右单旋转*/
static AVLTree SingleRotateRight(AVLTree k1)
{
	AVLTree k2;

	k2 = k1->rchild;
	k1->rchild = k2->lchild;
	k2->lchild = k1;

	k1->height =  Max(Height(k1->rchild),Height(k1->lchild))+1;
	k2->height =  Max(Height(k2->rchild),Height(k2->lchild))+1;
	return k2;
}

/*AVL树左双旋转*/
static AVLTree DoubleRotateLeft(AVLTree k1)
{
	k1 = SingleRotateRight(k1->lchild);
	return SingleRotateLeft(k1);
}

/*AVL树右双旋转*/
static AVLTree DoubleRotateRight(AVLTree k1)
{
	k1 = SingleRotateLeft(k1->rchild);
	return SingleRotateRight(k1);
}

这里还需要了一个Max函数，我就不贴出来了，就是比较两个数，返回较大的数。写不出来去小学深造去吧！

我用前序遍历和中序遍历做一下测试，从1打到15，顺序输入，看看输出是什么情况：

int main()
{
	AVLTree T = NULL;
	int i=0;
	for (i=1;i<16;i++)
	{
		AVL_Insert(&T,i);
	}

	PreOrderTraverse(T);
	printf("\n\n");
	InOrderTraverse(T);
	getchar();
	getchar();
	return 0;
}

第一排是前序遍历结果，第二排是中序遍历！！！！！刚好是一颗3层的满二叉树！

我再倒着15到1输入看看结果是不是一样：

int main()
{
	AVLTree T = NULL;
	int i=0;
	for (i=15;i>=1;i--)
	{
		AVL_Insert(&T,i);
	}

	PreOrderTraverse(T);
	printf("\n\n");
	InOrderTraverse(T);
	getchar();
	getchar();
	return 0;
}

AVL树的定义和基本操作