平衡二叉樹（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]); }