二叉查找樹

二叉樹的重要應用-------二叉搜尋樹

二叉搜尋樹

樹中的每個結點X，他的左子樹中所有項的值都小于X的值，右子樹所有項的值都大于X的值

二叉搜尋樹操作

1. 樹中是否有X結點

2. 插入

   就像查找樹中是否有X結點那樣沿着樹查找，如果找到X，則做一些 “更新” ，否則就将X插入到周遊的路徑上的最後一點

   注：對于重複圓的插入可以通過在節點中記錄附加字段，以訓示此資料出現的頻率

   

   淺色節點為插入的路徑

//将k插入t樹中
void insert(AVLnode *&t,int k)
{
 if(t==NULL) t=new AVLnode(null,null,k); //設定新節點的左右孩子null，值k的構造函數
 if(x< value(t)) insert(t->left);
 if(x< value(t)) insert(t->left);
 if(x==value(t)) do something
}
           

1. 删除

   發現X結點為樹葉，删除X

   發現X結點有一個兒子，調整X父親的鍊指向X的兒子，删除X

   發現X結點有兩個兒子，整X父親的鍊指向X右子樹最小元素（或左子樹的最大元素），删除X，這時候就會變成第一種和第二種情況

   注：當删除的次數不多時，可以使用懶惰搜尋，被删除了的做一個标記

//删除t樹的k
bool delete(AVLnode *&t,int k)
{
 if(t==NULL) return false;//設定新節點的左右孩子null，值k的構造函數
 if(x< value(t)) delete(t->left,k);
 if(x> value(t)) delete(t->right,k);
 if(x==value(t))  deletethis(t);
 }
 void deletethis(AVLnode *&t)
 {
 	1. X結點為樹葉處理
 	2. X結點有一個兒子處理
 	3. X結點有兩個兒子處理
 }