平衡二叉樹
或者是一顆空樹，或者它的左右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差不超過1 。
bf（balance factor）
我們将二叉樹上節點的左子樹深度減去右子樹深度的值成為平衡因子。那麼平衡二叉樹上所有節點的平衡因子隻可能是-1,0,1.隻要二叉樹上有一個節點的平衡引子的絕對值大于1，則該二叉樹就是不平衡的。
距離插入節點最近的，且平衡因子的絕對值大于1的節點為根的子樹，我們成為最小不平衡子樹。最小不平衡子樹的樹根是我們操作平衡轉換的參照點，調整最小不平衡子樹，然後就可以達到平衡的效果。
首先要明白，如果需要調整平衡二叉樹，那麼這顆二叉樹肯定是剛剛開始不平衡的，我們隻需要調整因為插入新節點導緻的最小不平衡子樹的結構即可。
樹的節點結構，相比于二叉查找樹，增加一bf，用來存儲平衡因子。
[cpp] view plain copy
/* 二叉樹的二叉連結清單節點結構定義 */
typedef struct bitnode
{
int data;
int bf; /* 相對于二叉查找樹，增加了平衡因子bf */
struct bitnode *lchild, *rchild;
} bitnode, *bitree;
兩個基本操作，左旋和右旋。
右旋圖示：
代碼如下：
/* 對以p為根的二叉排序樹作右旋處理 */
/* 處理之後p指向新的樹根節點，即旋轉處理之前的左子樹的根節點 */
void r_rotate( bitree *p )
/*
l->rchild (節點2的右孩子) 為null l->rchild != null
例 : 3 例 ： 9 6
/ / \ / \
2 => 2 6 10 => 5 9
/ / \ / \ / / \
1 1 3 5 7 4 7 10
/
4
*/
bitree l;
l = (*p)->lchild;
(*p)->lchild = l->rchild; /* 容易忽視，将*p的左子樹的右子樹作為*p的左子樹（如果 l->rchild 不為空） */
l->rchild = (*p);
*p = l;
}
左旋圖示：
/* 對以p為根的二叉排序樹作左旋處理 */
/* 處理之後 p 指向新的樹根節點，即旋轉處理之前的右子樹的根節點 */
void l_rotate( bitree *p)
r->lchild (節點2的左孩子) 為null r->lchild != null
例 : 1 例 ： 9 15
\ / \ / \
2 => 2 6 15 => 9 17
\ / \ / \ / \ /
3 1 3 10 17 6 10 16
/
16
bitree r;
r = (*p)->rchild;
(*p)->rchild = r->lchild; /* 将 p 的右孩子的左孩子轉接到 p 的右孩子上，上述的将 10 接至 9 的右孩子上 */
r->lchild = *p;
*p = r;
兩個複雜調整：
右子樹插入新節點，導緻不平衡，但是不能夠通過簡單的左旋、右旋解決。
由于插入節點 8 導緻出現了最小不平衡子樹（樹根為 6 ），于是現将以 9 為根的樹右旋處理，達到圖15效果，然後，在将以 6 為根的樹左旋處理，最後二叉樹重新平衡，達到圖16的效果。
/* 右平衡處理 */
/* 對以指針t所指節點為根的二叉樹作右平衡旋轉處理，與左平衡相對 */
/* 本算法結束時，指針t指向新的根節點 */
/* 參照左平衡處理的圖示分析 */
void rightbalance( bitree *t )
bitree r, rl;
r = (*t)->rchild;
switch( r->bf )
{
case rh:
(*t)->bf = r->bf = eh;
l_rotate(t);
break;
case lh:
rl = r->lchild;
switch( rl->bf )
{
case lh:
(*t)->bf = eh;
r->bf = rh;
break;
case eh:
(*t)->bf = r->bf = eh;
case rh:
(*t)->bf = lh;
r->bf = eh;
}
rl->bf = eh;
r_rotate( &(*t)->rchild );
l_rotate( t );
}
2. 另一種複雜情況是在左子樹上插入了新節點，導緻不平衡，于是先左旋、再右旋。詳見代碼。
代碼如下：
/* 左平衡旋轉處理的函數代碼 */
/* 對以指針t所指節點為根的二叉樹作左平衡旋轉處理 */
/* 注意：函數被調用，傳入一個需要調整平衡性的子樹t。由于leftbalance函數被調用時候 */
/* 其實是已經确認目前子樹是不平衡狀态，且左子樹高度大于右子樹高度。 */
/* 換句話說，此時t的根節點應該是平衡因子bf的值大于 1 的數 */
void leftbalance( bitree *t )
bitree l, lr;
l = (*t)->lchild; /* l指向t的左子樹根節點 */
switch( l->bf )
/* 檢查t的左子樹的平衡度，并做相應的平衡處理 */
case lh: /* 新節點插入在t的左孩子的左子樹上，要作單向右旋處理 */
/*
8(*t) 5 8 5
/ \ / \ / \ / \
(l)5 9 4 8 or 5 9 4 8
/ \ =>(直接右旋) / / \ / \ =>(直接右旋) \ / \
4 6 3 6 9 4 6 3 6 9
/ \
3(新插入) 3(新插入)
*/
(*t)->bf = l->bf = eh;
r_rotate( t );
case rh: /* 新節點插入在t的左孩子的右子樹上，要做雙旋處理 */
lr = l->rchild;
switch( lr->bf )
/*
8 8 7
/ \ / \ / \
5 9 7 9 5 8
/ \ =>(先以5為根，單向左旋) / =>(以8為根，單向右旋) / \ \
4 7 5 4 6 9
/ / \
6 4 6
*/
(*t)->bf = rh;
l->bf = eh;
(*t)->bf = l->bf = eh;
/*
8 8 6
/ \ / \ / \
5 9 6 9 5 8
/ \ =>(先以5為跟，單向左旋) / \ =>(以8為跟，單向右旋) / / \
4 6 5 7 4 7 9
\ /
7 4
l->bf = lh;
lr->bf = eh;
l_rotate( &(*t)->lchild );
插入：（insert_avl）
插入函數結合了上面的做右平衡處理的方法，現在平衡二叉樹中查找是否已經存在該元素，如果已經存在，那麼不插入，否則，插入新節點，再通過對應的處理，使二叉樹保持平衡狀态，更新每個結點的平衡因子。
/* 若在平衡的二叉排序樹t中不存在和e有相同關鍵字的節點，則插入一個 */
/* 資料元素為e的新節點并傳回1，否則傳回0 。若因插入而使二叉排序樹 */
/* 失去平衡，則作平衡旋轉處理，布爾變量taller反應t是否長高 */
int insert_avl( bitree *t, int e, int *taller)
if( !(*t) )
/* 遞歸調用insert_avl函數，如果進入if語句，說明原二叉排序樹中不存在與e相等的結點 */
/* 故而，插入新結點，樹“長高”，置taller為true */
*t = ( bitree )malloc( sizeof(bitnode) );
( *t )->data = e;
( *t )->lchild = ( *t )->rchild = null;
( *t )->bf = eh;
*taller = true;
}
else
if( e == (*t)->data )
/* 書中已存在與e相等的節點，不需要再次插入 */
*taller = false;
return false;
else if( e < (*t)->data )
/* 應該繼續在t的左子樹中進行搜尋 */
if( !insert_avl( &(*t)->lchild, e, taller) )
/* 說明插入失敗，已經存在與e相等的節點，無需再次插入 */
return false;
if(*taller)
{
/* 已經插入到 t 的左子樹，且左子樹“長高” */
switch( (*t)->bf )
{
case lh:
/* 原本左子樹比右子樹高，則需要進行平衡處理 */
leftbalance(t);
*taller = false;
break;
case eh:
/* 原本左右子樹等高，現因左子樹增高而樹增高 */
(*t)->bf = lh;
*taller = true;
case rh:
/* 原本右子樹比左子樹高，現左右子樹等高 */
(*t)->bf = eh;
}
}
else
/* 應該繼續在t的右子樹中進行搜尋 */
if( !insert_avl( &(*t)->rchild, e, taller) )
if(*taller)
/* 已經插入到 t 的右子樹且右子樹“長高” */
/* 檢查 t 的平衡度 */
case lh:
(*t)->bf = eh;
*taller = false;
break;
(*t)->bf = rh;
rightbalance(t);
return true;
完整代碼：
#include<stdio.h>
#define lh +1 /* 左高 */
#define eh 0 /* 等高 */
#define rh -1 /* 右高 */
#define true 1
#define false 0
void order(bitree t)//中序輸出
{
if(t == null)
return ;
order(t->lchild);
printf("%d ", t->data);
order(t->rchild);
}
/ / \ / \
4
\ / \ / \
16
8(*t) 5 8 5
8 8 7
8 8 6
void main()
int i;
int a[] = {3,2,1,4,5,6,7,10,9,8};
bitree t = null;
int taller;
for( i = 0; i < 10; i++)
insert_avl(&t, a[i], &taller);
order(t);
printf("\n");
總結，待續……
作者：柒月