－二叉搜索樹
查找問題：靜態(tài)查找和動態(tài)查找，靜態(tài)查找可以用二分查找－判定樹伏尼，那么針對動態(tài)查找數(shù)據(jù)如何組織佑钾？
（樹的動態(tài)性強(qiáng) 比線性方便）
二叉搜索樹（BST，Binary Search Tree）也稱二叉排序樹或二叉查找樹
一棵二叉樹滿足以下性質(zhì)：
1.非空左子樹的所有鍵值小于其根結(jié)點的鍵值
2.非空右子樹的所有鍵值大于其根結(jié)點的鍵值
3.左烦粒、右子樹都是二叉搜索樹
－二叉樹的特殊函數(shù)：
二叉搜索樹的查找操作（找出指定元素）：Find
Position Find ( ElementType X, BinTree BST )
{
if ( ! BST ) return NULL ; // 查找失敗
if ( X > BST -> Data )
return Find ( X, BST -> Right ); // 在右子樹中繼續(xù)查找
Else if ( x < BST -> Data )
return Find ( x, BST -> Left ); // 在左子樹中繼續(xù)查找
else // X == BST -> Data
return BST; // 查找成功休溶，返回找到結(jié)點的地址
}
上述算法運用到遞歸且都是尾遞歸，即在程序最后要返回時才遞歸扰她，從編譯角度看兽掰，尾遞歸可以用循環(huán)實現(xiàn)。
前文提到非遞歸函數(shù)執(zhí)行效率更高徒役，所以將“尾遞歸”函數(shù)改為迭代函數(shù)：
Position Find ( ElementType X, BinTree BST )
{
while ( BST ) {
if ( X > BST -> Data )
BST = BST -> Right; // 向右子樹移動并查找
else if ( X < BST -> Data )
BST = BST -> Left; // 向左子樹移動并查找
else // X == BST -> Data
return BST; // 查找成功孽尽，返回結(jié)點地址
}
return NULL; // 查找失敗
}
查找效率決定于樹的高度
查找最大值和最小值，即最左結(jié)點和最右結(jié)點
－二叉搜索樹的插入
關(guān)鍵是找到元素應(yīng)該插入的位置忧勿，可以采用與Find函數(shù)相似的方法杉女，
BinTree Insert ( ElementType X, BinTree BST )
{
if ( ! BST ) {
// 若帶插入的二叉搜索樹為空樹，則生成并返回只有一個結(jié)點的二叉搜索樹鸳吸；若帶插入的二叉搜索樹不為空樹熏挎，則代表已經(jīng)找到了應(yīng)該插入的位置，就在該位置插入指定的元素
BST = malloc ( sizeof ( struct TreeNode ) );
BST -> Data = X;
BST -> Left = BST -> Right = NULL;
} else // 開始查找應(yīng)該插入的位置
if ( X < BST -> Data )
BST -> Left = Insert ( X, BST -> Left ); // 遞歸插入左子樹
Else if ( x > BST -> Data )
BST -> Right = Insert ( X, BST -> Right ); // 遞歸插入右子樹
return BST; // else X已存在 什么都不用做
}
－二叉搜索樹的刪除
要考慮三種情況：
1.要刪除的是葉結(jié)點：直接刪除 并修改其父結(jié)點指針 值為NULL
2.要刪除的結(jié)點只有一個子結(jié)點：將其父結(jié)點的指針指向要刪除結(jié)點的孩子結(jié)點
3.最復(fù)雜的情況晌砾，要刪除的結(jié)點有左右兩棵子樹坎拐，用另一結(jié)點替代被刪除結(jié)點：右子樹的最小元素或者左子樹的最大元素，即將該情況轉(zhuǎn)換為前面兩種情況养匈，右子樹的最小元素或者左子樹的最大元素必然是葉結(jié)點或者只有一個子結(jié)點的結(jié)點 要刪除它們是比較方便的
BinTree Delete ( ElementType X, BinTree BST )
{
Position Tmp ;
if ( ! BST ) printf ( “要刪除的元素未找到” ) ;
else if ( X < BST -> Data )
BST -> Left = Delete ( X, BST -> Left ); // 左子樹遞歸刪除
else if ( x > BST -> Data )
BST -> Right = Insert ( X, BST -> Right ); // 右子樹遞歸刪除
else // 找到要刪除的結(jié)點哼勇，接下來判斷該結(jié)點的子結(jié)點情況
if ( BST -> Left && BST -> Right ) { // 要被刪除的結(jié)點有左右兩個子結(jié)點
Tmp = FindMin ( BST -> Right ) ; // 在右子樹中找最小的元素填充刪除結(jié)點
BST -> Data = Tmp -> Data ;
BST -> Right = Delete ( BST -> Data, BST -> Right ) ; // 在刪除結(jié)點的右子樹中刪除最小元素
} else { // 被刪除結(jié)點有一個子結(jié)點或無子結(jié)點
Tmp = BST ;
if ( !BST -> Left ) // 有右孩子活著無子結(jié)點
BST = BST -> Right ;
else if ( ! BST -> Right ) ; // 有左孩子或無子結(jié)點
BST = BST -> Left ;
free ( Tmp ) ;
}
return BST ;
}
－平衡二叉樹
搜索樹結(jié)點不同插入次序，將導(dǎo)致不同的深度和平均查找長度ASL呕乎；平均查找長度ASL＝（層數(shù)＊該層結(jié)點數(shù) 的和）／總結(jié)點數(shù)
平衡因子（Balance Factor）：左子樹的高度與右子樹的高度的差
平衡二叉樹（Balance Binary Tree）（AVL樹）：空樹积担，或者任一結(jié)點左右子樹高度差的絕對值不超過1
－平衡二叉樹的調(diào)整：
當(dāng)我們往平衡二叉樹中插入結(jié)點后，可能導(dǎo)致插入后的樹不平衡猬仁，這時我們需要調(diào)整
右單旋：首先找出不平衡的“發(fā)現(xiàn)者”（左右子樹高度差大于1的結(jié)點）“麻煩結(jié)點”（插入后導(dǎo)致不平衡的結(jié)點）在發(fā)現(xiàn)者右子樹的右邊帝璧，因而叫RR插入，需要RR旋轉(zhuǎn)（右單旋）
上面例子中發(fā)現(xiàn)者是5逐虚， 麻煩結(jié)點是15
左單旋：類似的聋溜，左單旋即“麻煩結(jié)點”在“發(fā)現(xiàn)者”左子樹的左邊，因而叫LL插入叭爱，需要LL旋轉(zhuǎn)（左單旋）
LR旋轉(zhuǎn)：“麻煩結(jié)點”在“發(fā)現(xiàn)者”左子樹的右邊撮躁，因而叫LR插入，需要LR旋轉(zhuǎn)
RL旋轉(zhuǎn)：“麻煩結(jié)點”在“發(fā)現(xiàn)者”右子樹的左邊买雾，因而叫RL插入把曼，需要RL旋轉(zhuǎn)
