夕拾算法进阶篇：25)平衡二叉树(AVL算法)

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。其中左子树和右子树的高度差称为平衡因子。

只有每个结点的平衡因子的绝对值都不超过1，排序二叉树才是AVL树，由于需要计算每个结点的平衡因子，因此在树结构中添加一个变量height，用来记录当前结点为根节点的子树的高度：

//树结构定义 struct Node{	int data,height;	Node *lchild,*rchild; }; //简单封装下新建节点的操作 Node* newNode(int x){	Node* n=new Node();	n->data=x;	Node->height=1; //初始化结点的高度为1 	n->lchild=n->rchild=NULL; 	return n; }显然，可以通过下面的函数获得结点root所在的当前高度：
//获取以root结点为根节点的当前height int getHeight(Node *root){	if(root==NULL)		return 0; //空结点高度为0	return root->height;}根据定义，通过下面的函数计算平衡因子：
//计算平衡因子 getBalanceFactor(Node *root){	return getHeight(root->lchild)-getHeight(root->rchild);} 为什么不直接记录平衡因子，而是记录高度？因为没有办法通过当前结点的子树的平衡因子计算得到该结点的平衡因子，而需要借助子树的高度间接求得(子树的高度固定)。显然，结点root所在子树的heigth等于其左子树大的height和右子树的height的较大值加1，因此可以通过下面的函数来更新height
//更新root结点的heightvoid updateHeight(Node* root){	//max(左孩子的height,右孩子的height)+1	root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;} 
这里介绍用AVL算法来构造平衡二叉树，看一个案例：如下左图的排序二叉树所示，其中☆是结点A的左子树，◆和◇分别是B的左右子树。本来大家相安无事，但有一天B突然觉得，既然A的权值比自己小，凭什么让A作为根结点呢？于是B找A商量，想自己做根节点，A便同意了，但是由于基因的左右，他们讲保证调整后的树仍然是一棵排序二叉树。
显然，☆的上所有的节点的权值都比A小，◇上所有的点都比B大，因此不需要对☆和◇做调整(保存原来的位置不动)，那么◆是否需要调整呢？当然需要，因为调整后B的左孩子将是结点A，因此必须把◆移动到其他的地方去。移动到哪呢？考虑到A、B、◆的权值满足A<◆<B，于是让◆成为结点A的右子树即可。而这个过程，我们称为左旋，其具体步骤如下：
(1)让B的左子树◆称为A的右子树
(2)让A成为B的左子树
(3)将B设置为根结点
如下给出左旋的代码：
//左旋void leftRotation(Node* root){	Node *temp=root->rchild //root指向A节点，temp指向B节点	root->rchild=temp->lchild; //步骤1 	temp->lchild=root;  //步骤2	updateHeight(root); //更新结点A的高度	updateHeight(temp); //更新结点B的高度 	root=temp; //步骤3} 
既然有左旋当然就会有右旋，左旋的逆过程就是右旋。右旋过程可以类比左旋，其只不过交换了A与B、左与右。其代码如下
//右旋void rightRotation(Node* root){	Node *temp=root->lchild //root指向B节点，temp指向A节点	root->rchild=temp->rchild; //步骤1 	temp->rchild=root;  //步骤2	updateHeight(root); //更新结点B的高度	updateHeight(temp); //更新结点A的高度 	root=temp; //步骤3} 
树型LL的含义：在失衡结点X(之前是平衡的)的左孩子的左子树上插入结点导致结点X不平衡树型LR的含义：在失衡结点X(之前是平衡的)的左孩子的右子树上插入结点导致结点X不平衡树型RR的含义：在失衡结点X(之前是平衡的)的右孩子的右子树上插入结点导致结点X不平衡树型RL的含义：在失衡结点X(之前是平衡的)的右孩子的左子树上插入结点导致结点X不平衡
树的具体旋转过程可以参考这个博客(http://blog.csdn.net/a454042522/article/details/8591421)，可以证明，只要把靠近插入结点的失衡结点调整到正常，路径上所有的结点就都会平衡。这里给出AVL树插入的情况汇总(BF表示平衡因子)
树形
判断条件
调整方法
LL
BF(root)=2,BF(root->lchild)=-1
对root进行右旋
LR
BF(root)=2,BF(root->lchild)=-1
对root->lchild进行左旋，再对root进行右旋
RR
BF(root)=-2,BF(root->lchild)=-1
对root进行左旋
RL
BF(root)=-2,BF(root->lchild)=-1
对root->rchild进行右旋，再对root进行左旋
现在考虑如何书写插入代码，首先AVL树的插入代码是在排序二叉树的插入代码的基础上加上平衡的操作，在这个基础上，由于需要从插入的结点从下往上判断结点是否失衡，因此需要在每个insert函数之后，在回溯时更新当前子树的高度，并在这之后根据树型是LL型、LR型、RR型、RL型来进行平衡操作，代码如下
void insert(Node* &root,int x){	if(root==NULL){ //空树查找失败，即插入的位置 		root=newNode(x); 	}else if(root->data>=x){//x节点比根节点小，说明x需要插在左子树 		insert(root->lchild,x);//往左子树搜索x 		updateHeight(root); //在回溯的时候，更新树高度		if(getBalanceFactor(root)==2){			if(getBalanceFactor(root->lchild)==1){//LL型				rightRotation(root); 			}else if(getBalanceFactor(root->lchild)==1) { //LR型 				leftRotation(root->lchild);				rightRotation(root);			}		} 	}else {//x节点比根节点大，说明x需要插在右子树 		insert(root->rchild,x);//往右子树搜索x 		updateHeight(root); //在回溯的时候，更新树高度		if(getBalanceFactor(root)==2){			if(getBalanceFactor(root->rchild)==1){//RR型				leftRotation(root); 			}else if(getBalanceFactor(root->rchild)==1) { //RL型 				rightRotation(root->rchild);				leftRotation(root);			}		} 	}}AVL树的建立就是不断地插入新结点的过程
int a[6]={1,3,5,4,6,2};Node *root=NULL; //root初始为空 for(int i=0;i<6;i++){	insert(root,a[i]); }