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