二叉查找樹是這樣一種數據結構：它是按二叉樹的結構來組織的，節點除了key域外，還包含有left、right和p指針，分別指向自己的左孩子、右孩子和父親節點。如果兒子或者父親不存在，則該指針置NULL。二叉查找樹又稱為二叉排序樹。
二叉查找樹中關鍵字的存儲方式總是滿足：
設x為二叉查找樹中的一個節點，如果y是x的左子樹中的任意一個節點，則key[y] <= key[x]；如果y是x的右子樹中的任意一個節點，則key[y] >= key[x]。因此如果對一棵二叉查找樹進行中序遍歷的話那么輸出的結果將是升序排列的。
一、中序遍歷二叉樹其算法是簡單的，遞歸算法如下：
1 INORDER-TREE-WALK(x)
2 if x != NULL
3 then
4 INORDER-TREE-WALK(left[x])
5 print key[x]
6 INORDER-TREE-WALK(right[x])
定理：如果x是一棵包含n個節點的子樹的根，則調用INORDER-TREE-WALK(x)過程的時間為
θ(n)。
利用遞推公式證明還是相對簡單的，略。
二、查詢二叉查找樹
1、查找指定關鍵字k
給定指向樹根的指針和關鍵字k，返回包含關鍵字k的指針或者NULL，遞歸算法如下：
1 TREE-SEARCH(x, k)
2 if x == NULL or k == key[x]
3 then
4 return x
5 if k < key[x]
6 then
7 return TREE-SEARCH(left[x], k)
8 else
9 return TREE-SEARCH(right[x], k)
非遞歸版本的算法如下：
1 INTERATIVE-TREE-SEARCH(x, k)
2 while x != NULL and k != key[x]
3 do
4 if k < key[x]
5 then
6 x = left[x]
7 else
8 x = right[x]
9 return x
算法復雜度相同，均為O(h)，其中h為樹的高度。
2、最大關鍵字元素和最小關鍵字元素函數TREE-MINIMUM(x)和TREE-MAXIMUM(x)分別返回二叉查找樹的最小關鍵字元素和最大關鍵字元素，思想也是簡單的，沿著二叉查找樹的left指針一直走下去直到left指針為空，則當前節點為最小關鍵字元素；沿著二叉查找樹的right指針一直走下去直到right指針為空，則當前節點為最大關鍵字元素。復雜度也相同，均問O(h)。
算法如下：
1 TREE-MINIMUM(x)
2 while left[x] != NULL
3 do
4 x = left[x]
5 return x
6
7 TREE-MAXIMUM(x)
8 while right[x] != NULL
9 do
10 x = right[x]
11 return x
3、前趨與后繼當找尋一個二叉查找樹的中序遍歷后繼節點的時候，有下面兩種情況：
- 如果當前節點的right指針不為NULL，則說明節點有右子樹，由于是中序遍歷，因此當前節點的后繼節點必然是其右子樹中關鍵字值最小的節點，這通過TREE-MINIMUM(right[x])即可得到；
- 如果當前節點的right指針為NULL，則說明節點沒有右子樹，此時情況稍微有些復雜，可以畫圖理解一下，其實就是如下情況，沿著當前節點的父指針往上走，只要此節點是是其父節點的右孩子，就繼續往上走，直到此節點是其父節點的左孩子或者此節點為空為止，返回此節點的父節點或者NULL。
用圖形表示如下：
我們可以看到，如果節點的right[x]為空，則y節點必是x節點的后繼節點，除非不包含符合這一條件的y節點，則x的后繼節點為NULL。
由此算法如下：
1 TREE-SUCCESSOR(x)
2 if right[x] != NULL
3 then
4 return TREE-MINIMUM(right[x])
5 y = p[x]
6 while y!= NULL and x == right[y]
7 do
8 x = y
9 y = p[y]
10 return y
同理，求節點x的前趨類似：
- 如果當前節點的left指針不為NULL，則說明節點有左子樹，當前節點的前趨節點必然是其左子樹中關鍵字值最大的節點，這通過TREE-MAXIMUM(left[x])即可得到；
- 如果當前節點的left指針為NULL，則說明節點沒有左子樹，此時為如下情況，沿著當前節點的父指針往上 走，只要此節點是是其父節點的左孩子，就繼續往上走，直到此節點是其父節點的右孩子或者此節點為空為止，返回此節點的父節點或者NULL。
由此算法如下：
1 TREE-PREDECCESSOR(x)
2 if left[x] != NULL
3 then
4 return TREE-MAXIMUM(left[x])
5 y = p[x]
6 while y != NULL and x == left[y]
7 do
8 x = y
9 y = p[y]
10 return y
兩個算法時間復雜度相同，均為O(h)。
三、二叉查找樹的插入和刪除1、插入對于二叉查找樹的插入操作，相對簡單，只需要從二叉查找樹的根開始向下查找應該插入的位置即可。這個應該插入的位置必然為一葉子節點的left指針或者right指針指向的空域。算法如下：
1 TREE-INSERT(T, z)
2 y = NULL //y指向當前節點的父節點
3 x = root[T] //指向當前節點
4 while x != NULL
5 do
6 y = x
7 if key[z] < key[x]
8 then
9 x = left[x]
10 else
11 x = right[x]
12 p[z] = y
13 if y == NULL //如果為空樹
14 then
15 root[T] == z //樹根則為z
16 else if key[z] < key[y]
17 then
18 left[y] = z
19 else
20 right[y] = z
算法復雜度為O(h)。
2、刪除對于刪除一個節點，則情況復雜很多，因為刪除操作破壞了二叉查找樹的結構，必須調整樹的結構，仔細觀察發現，不外乎以下三種情況：
- 如果要刪除的節點的左右孩子均為空，則直接刪除該節點即可，因為這樣并沒有破壞二叉查找樹的結構；
- 如果要刪除的節點只有一個孩子（為左孩子或者右孩子均可），則直接將要刪除節點的父節點的left指針或者right指針指向要刪除節點的孩子節點即可，同時將孩子節點的父指針指向要刪除節點的父節點；
- 如果要刪除的節點既有左子樹又有右子樹，則將要刪除節點用其后繼節點替換，并刪除后繼節點即可。
為此算法如下：
1 TREE-DELETE(T, z)
2 if left[z] == NULL or right[z] == NULL
3 then //y指向真正需要刪除的節點
4 y = z //y要么為要刪除的節點
5 else
6 y = TREE-SUCCESSOR(z) //y要么為要刪除節點的后繼節點
7 if left[y] != NULL
8 then
9 x = left[y]
10 else
11 x = right[y]
12 if x != NULL
13 then
14 p[x] = p[y]
15 if p[y] == NULL
16 then
17 root[T] = x
18 else if y == left[p[y]]
19 then
20 left[p[y]] = x
21 else
22 right[p[y]] = x
23 if y != z
24 then
25 key[z] = key[y]
26 return y
時間復雜度同樣為O(h)。
四、隨機構造的二叉查找樹性能分析
posted on 2011-10-31 16:28
myjfm 閱讀(340)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎