二叉查找樹的定義、周遊與查找
定義
二叉查找樹( )或者是一棵空樹，或者是具有下列性質的二叉樹：
- 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
- 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
- 它的左、右子樹也分别為二叉查找樹。
上述性質被稱為性質
可以看出，二叉查找樹是遞歸定義的
如圖是一個二叉查找樹。
下述代碼給出了一個節點的定義。
struct BST_Node {
BST_Node *left, *right;//節點的左右子樹的指針
int value; //節點的值
}; 周遊
對于一個已知的二叉查找樹，從小到大輸出其節點的值，隻需對其進行二叉樹的中序周遊，即遞歸地先輸出其左子樹，再輸出其本身，然後輸出其右子樹
周遊的時間複雜度為
下述代碼為把一個以為根的所有節點的值從小到大輸出到标準輸出流。
BST_Node *root;
void BST_Print(BST_Node *P) {
if (P) {
BST_Print(P->left);
printf(“%d\n”, P->value);
BST_Print(P->right);
}
}
int main() {
BST_Print(root);
return 0;
} 查找
對于一個已知的二叉查找樹，在其中查找特定的值，方法如下。
- 從根節點開始查找；
- 如果目前節點的值就是要查找的值，查找成功；
- 如果要查找的值小于目前節點的值，在目前節點的左子樹中查找該值；
- 如果要查找的值大于目前節點的值，在目前節點的右子樹中查找該值；
- 如果目前節點為空節點，查找失敗，二叉查找樹中沒有要查找的值。
查找的期望時間複雜度為
下述代碼為在一個已知的二叉查找樹中查找值。
BST_Node *root;
BST_Node *BST_Find(BST_Node *P, int value) {
if (!P) return 0; //查找失敗
if (P->value == value) return P; //查找成功
else if (value < P->value) return BST_Find(P->left, value); //在左子樹中查找
else return BST_Find(P->right, value); //在右子樹中查找
}
int main() {
BST_Node *result;
result = BST_Find(root, 5);//在BST中查找值為5的節點
if (result) printf("Found!");
else printf("Not Found!");
return 0;
} 二叉查找樹的插入與删除
插入
在二叉查找樹中插入元素，要建立在查找的基礎上
基本方法是類似于線性表中的二分查找，不斷地在樹中縮小範圍定位，最終找到一個合适的位置插入
具體方法如下所述。
- 從根節點開始插入；
- 如果要插入的值小于等于目前節點的值，在目前節點的左子樹中插入；
- 如果要插入的值大于目前節點的值，在目前節點的右子樹中插入；
- 如果目前節點為空節點，在此建立新的節點，該節點的值為要插入的值，左右子樹為空，插入成功。
對于相同的元素，一種方法我們規定把它插入左邊，另一種方法是我們在節點上再加一個域，記錄重複節點的個數
上述方法為前者
插入的期望時間複雜度為。
下述代碼為在一個二叉查找樹中插入值。
BST_Node *root;
BST_Node *BST_Insert(BST_Node *&P,int value) {//節點指針要傳遞引用
if (!P) {
P = new BST_Node; //插入成功
P->value = value;
}
else if (value <= value) return BST_Insert(P->left, value); //在左子樹中插入
else return BST_Insert(P->right, value); //在右子樹中插入
}
int main() {
BST_Insert(root, 5);//在 BST 中插入值 5
return 0;
} 删除
二叉查找樹的删除稍有些複雜，要分三種情況分别讨論
基本方法是要先在二叉查找樹中找到要删除的節點的位置，然後根據節點分以下情況：
- 情況一，該節點是葉節點(沒有非空子節點的節點)，直接把節點删除即可。
- 情況二，該節點是鍊節點(隻有一個非空子節點的節點)，為了删除這個節點而不影響它的子樹，需要把它的子節點代替它的位置，然後把它删除。如圖所示，删除節點時，需要把它的左子節點代替它的位置。
- 情況三，該節點有兩個非空子節點。由于情況比較複雜，一般的政策是用它右子樹的最小值來代替它，然後把它删除。如圖所示，删除節點時，在它的右子樹中找到最小的節點，該節點一定為待删除節點的後繼。删除節點(它可能是葉節點或者鍊節點)，然後把節點的值改為。
實際上在實作的時候，情況一和情況二是可以一樣對待的，因為用葉節點的子節點代替它本身，就是用空節點代替了它，等同于删除
對待情況三除了可以用後繼代替本身以外，我們還可以使用它的前驅(左子樹的最大值)代替它本身
這就牽涉到了查找最小值的問題，基本方法就是從子樹的根節點開始，如果左子節點不為空，那麼就通路左子節點，直到左子節點為空，目前節點就是該子樹的最小值節點，删除它隻需用它的右子節點代替它本身。
下述代碼是在一個給定的二叉查找樹中删除值。
BST_Node *root;
int Find_DeleteMin(BST_Node *&P) {//傳回子樹的最小值并删除 節點指針要傳遞引用
if (!P->left) {//如果已經沒有左子節點，删除它
BST_Node *t = P;
int r = P->value;
P = P->right;
delete t;
return r;
}
else return Find_DeleteMin(P->left); //如果還有左子節點，通路左子節點
}
void BST_Delete(BST_Node *&P, int value)//節點指針要傳遞引用
{
if (!P) return ; //查找失敗，BST 中不存在要删除的節點
if (P->value == value) {//查找成功，對其删除
if (P->left and P->right) P->value = Find_DeleteMin(P->right);
else {
BST_Node *t = P;
if (P->left) P = P->left;
else P = P->right;
delete t;
}
}
else if (value < P->value) BST_Delete(P->left, value); //在左子樹中查找
else BST_Delete(P->right, value); //在右子樹中查找
}
int main() {
BST_Delete(root, 2);//在 BST 中删除值 2
return 0;
} 二叉查找樹的平衡性問題讨論
二叉查找樹的效果究竟如何？
事實上，随機的進行次插入和删除之後，二叉查找樹會趨向于向左偏沉
為什麼會出現這種情況，原因是在于删除時，我們總是選擇将待删除節點的後繼代替它本身
這樣就會造成總是右邊的節點數目減少，以至于樹向左偏沉
已經被證明，随機插入或删除次以後，樹的期望深度為
我們可以在删除時随機地選擇用前驅還是後繼代替本身，以消除向一邊偏沉的問題
這種神奇地做法消除了偏沉的不平衡，效果十分明顯
對待随機的資料二叉查找樹已經做得很不錯了，但是如果有像這樣有序的資料插入樹中時，會有什麼後果出現？
如圖
二叉查找樹退化成為了一條鍊
這個時候，無論是查找、插入還是删除，都退化成了的時間
事實上，在實際的應用中，這種情況會經常出現，而簡單的二叉查找樹卻沒有辦法變得更快
我們需要使二叉查找樹變得盡量平衡，才能保證各種操作在的期望時間内完成，于是各種自動平衡二叉查找樹（ ）因而誕生
在常見的自動平衡二叉查找樹（以下簡稱平衡樹）中，有近乎完美平衡的樹（ & ），紅黑樹（ ）和（ ）等，以及期望平衡的伸展樹（ ）和（ & ）等資料結構。