热门问题
时间线
聊天
视角
二元搜尋樹
一種支援查詢等操作的二元樹 来自维基百科,自由的百科全书
Remove ads
二叉搜索樹(英語:binary search tree,簡稱BST)[a]是一種有根二叉樹數據結構。它要求每個內部節點的鍵值都大於其左子樹中所有節點的鍵值,且都小於其右子樹中所有節點的鍵值。該樹各項操作時間複雜度均與樹的高度成線性關係。
Remove ads

二叉搜索樹每次比較都能排除大約一半的剩餘節點,故能以對數時間查找、插入、刪除數據。但其性能依賴於節點的插入順序,插入隨機鍵值時仍能維持對數級別,但在最壞情況下會退化成鍊表。為保證效率,研究者發明了多種平衡樹,能將最壞查找複雜度維持在。
Remove ads
歷史
二叉搜索樹最早由多位研究者獨立提出,包括P.F.溫德利、安德魯·唐納德·布思、安德魯·科林、托馬斯·N·希巴德。[6][7]這種數據結構常被歸功於康威·柏納-李及大衛·惠勒,他們在1960年將之用於磁帶上帶標籤數據的存儲。[8]希巴德實現二叉搜索樹的方法也是最早廣為流傳的一種。[6]
若按任意順序插入節點,樹的高度可能接近節點數,導致操作效率急劇下降。研究者們發明了平衡樹(即能夠自平衡的二叉搜索樹),將樹的高度限制在以內。[9]:458–459同時,相關人員也提出了多種高度平衡的二叉搜索樹結構,例如AVL樹、樹堆、紅黑樹等。[10]其中,AVL樹是首類平衡樹,[11]由格奧爾吉·阿傑爾松-韋利斯基及葉夫根尼·蘭迪斯於1962年發明,用於高效組織信息。[12][13]
Remove ads
性質
二叉搜索樹為有根的二叉樹,其節點順序為嚴格全序關係,每個節點都滿足:左子樹上所有節點的鍵值都小於該節點,右子樹上所有節點的鍵值都大於該節點。這一結構保證可以在對數時間內定位任意鍵值。[14]:298[15]:287[1]:161-162除查找外,其也常用於排序,但性能取決於節點的插入和刪除順序——在最壞情況下,連續操作可能使樹退化為類似單鍊表的結構,這時的查找複雜度與鍊表相同。[14]:299-302[16]
遍歷
二叉搜索樹的遍歷有三種基本方法:前序、中序、後序。[15]:287[1]:162
- 中序遍歷:依次遍歷左子樹、根節點、右子樹。遍歷結果為鍵值遞增順序。
- 前序遍歷:依次遍歷根節點、左子樹、右子樹。
- 後序遍歷:依次遍歷左子樹、右子樹、根節點。
以下是遞歸實現的遍歷偽代碼:[15]:287–289[1]:162
Inorder-Tree-Walk(x) if x ≠ NIL then Inorder-Tree-Walk(x.left) visit node Inorder-Tree-Walk(x.right) end if |
Preorder-Tree-Walk(x) if x ≠ NIL then visit node Preorder-Tree-Walk(x.left) Preorder-Tree-Walk(x.right) end if |
Postorder-Tree-Walk(x) if x ≠ NIL then Postorder-Tree-Walk(x.left) Postorder-Tree-Walk(x.right) visit node end if |
操作
在二叉搜索樹中查找某個特定的鍵,可以使用遞歸或迭代方式實現。
查找過程從樹的根節點開始:
- 如果根節點為空(),說明該鍵不存在。
- 如果根節點的鍵值與目標鍵值相等,返回該節點,表示查找成功。
- 如果目標鍵值小於根節點的鍵值,則繼續在左子樹中查找;
- 如果目標鍵值大於根節點的鍵值,則繼續在右子樹中查找。
重複上述步驟,直到找到該鍵,或者剩餘子樹為空。若到達空子樹仍未找到,說明該鍵不存在於樹中。[15]:290-291[1]:163
以下偽代碼展示遞歸方式實現的查找過程:[15]:290[1]:163
Recursive-Tree-Search(x, key) if x = NIL or key = x.key then return x if key < x.key then return Recursive-Tree-Search(x.left, key) else return Recursive-Tree-Search(x.right, key) end if |
遞歸會一直進行,直到遇到或是找到目標鍵。
Remove ads
遞歸過程也可展開為循環形式,一般情況下循環版本的效率更高。其偽代碼如下:[15]:291[1]:163
Iterative-Tree-Search(x, key) while x ≠ NIL and key ≠ x.key do if key < x.key then x := x.left else x := x.right end if repeat return x |
由於查找可能會一直到葉節點,因此時間複雜度為樹的高度(為樹的高度)。[15]:290[1]:163在最壞情況下,一棵嚴重不平衡的二叉搜索樹可能退化成單鍊表,這時複雜度會達到(為樹中節點總數)。但對於高度平衡的二叉搜索樹而言,複雜度為。[9]:458–459[17]:403[2]:255
Remove ads
在某些場景下,需要查找給定節點的「後繼」或「前驅」。後繼節點是大於該節點鍵值的節點中,鍵值最小的那一個;前驅節點是小於該節點鍵值的節點中,鍵值最大的那一個。以下偽代碼給出求節點的後繼與前驅方法:[18][19][15]:292–293[1]:164
BST-Successor(x) if x.right ≠ NIL then return BST-Minimum(x.right) end if y := x.parent while y ≠ NIL and x = y.right do x := y y := y.parent repeat return y |
BST-Predecessor(x) if x.left ≠ NIL then return BST-Maximum(x.left) end if y := x.parent while y ≠ NIL and x = y.left do x := y y := y.parent repeat return y |
尋找樹中鍵值最大或最小的節點,是尋找後繼與前驅過程中的重要環節。其偽代碼如下:[15]:291–292[1]:163–164
BST-Maximum(x) while x.right ≠ NIL do x := x.right repeat return x |
BST-Minimum(x) while x.left ≠ NIL do x := x.left repeat return x |
Remove ads
若在節點中維護以之為根節點的子樹的節點總數,則可實現選擇與排名操作。選擇操作用於在樹中直接定位排名為的節點,即第小的鍵。[17]:406–407[2]:257–258排名操作則與之相對,給定指定鍵後,其會返回小於該鍵的節點數。[17]:408[2]:258–259這兩種操作的偽代碼如下:[17]:409[2]:258–259
Select‑By‑Rank(T, k) return Select(T.root, k) Select(x, k) if x = NIL then return NIL end if t := size(x.left) if t > k then return Select(x.left, k) else if t < k then return Select(x.right, k − t − 1) else return x end if |
Rank-In-Tree(T, key) return Rank(key, T.root) Rank(key, x) if x = NIL then return 0 cmp := compare(key, x.key) if cmp < 0 then return Rank(key, x.left) else if cmp > 0 then return 1 + size(x.left) + Rank(key, x.right) else return size(x.left) end if |
其中size
表示子樹規模信息,即子樹中節點數量。
利用中序遍歷,可以實現範圍查找,即查詢兩個給定值之間的元素數量。其偽代碼如下:[17]:412–413[2]:261–262
Range-Query(x, lo, hi, list) if x = NIL then return end if if lo < x.key then Range-Query(x.left, lo, hi, list) end if if lo ≤ x.key ≤ hi then list.append(x.key) end if if hi > x.key then Range-Query(x.right, lo, hi, list) end if |
Remove ads
二叉搜索樹的數據結構會隨插入和刪除操作而變化。插入操作須保證二叉搜索樹的性質不會遭到破壞,且插入的節點總是作為葉節點加入。[15]:294–295[1]:165–166以下偽代碼給出迭代形式的插入過程:[15]:294[1]:165–166
1 BST-Insert(T, z) 2 y := NIL 3 x := T.root 4 while x ≠ NIL do 5 y := x 6 if z.key < x.key then 7 x := x.left 8 else 9 x := x.right 10 end if 11 repeat 12 z.parent := y 13 if y = NIL then 14 T.root := z 15 else if z.key < y.key then 16 y.left := z 17 else 18 y.right := z 19 end if |
過程使用變量作為遍歷節點的父節點(追蹤指針)。初始時如果為,說明樹為空,新節點即作為樹的根;否則,需根據節點鍵值大小關係插入對應位置。[15]:295[1]:166
Remove ads

從樹中刪除某個節點時,需分三種情況處理:[15]:295-297[1]:166-167
- 是葉節點:直接用空指針替換即可。(如圖中(a))
- 僅有一個子節點:用的子節點替換。(如圖中(b)、(c))
- 有兩個子節點:用的中序遍歷所得到的後繼或前驅代替。此處以後繼為例:
- 如果恰好是的右子節點:直接用取代,的右子樹保持不變。(如圖中(d))
- 如果位於的右子樹內部:先用的右子節點替換,再用替代。(如圖中(e))
以下偽代碼實現刪除操作:[15]:296-298[1]:167-168
1 BST-Delete(BST, z) 2 if z.left = NIL then 3 Shift-Nodes(BST, z, z.right) 4 else if z.right = NIL then 5 Shift-Nodes(BST, z, z.left) 6 else 7 y := BST-Successor(z) 8 if y.parent ≠ z then 9 Shift-Nodes(BST, y, y.right) 10 y.right := z.right 11 y.right.parent := y 12 end if 13 Shift-Nodes(BST, z, y) 14 y.left := z.left 15 y.left.parent := y 16 end if |
1 Shift-Nodes(BST, u, v) 2 if u.parent = NIL then 3 BST.root := v 4 else if u = u.parent.left then 5 u.parent.left := v 5 else 6 u.parent.right := v 7 end if 8 if v ≠ NIL then 9 v.parent := u.parent 10 end if |
過程根據上述3種情況處理節點刪除:第1種情況(葉節點)對應第2—3行;第2種情況(單個子節點)對應第4—5行;第3種情況(有兩個子節點)對應第6—16行。輔助函數用於把節點替換成。[15]:296-298[1]:167-168
若在第3種情況中,僅選用後繼或前驅節點中的一種,則並未考慮到樹的對稱性,可能會導致性能問題。若要避免此問題,可以隨機選擇使用後繼或前驅。[17]:410[2]:260
平衡樹
普通的二叉搜索樹中,若不加以平衡,插入或刪除操作可能會導致樹退化。[20]若是使用隨機鍵值構建二叉搜索樹,那麼平均高度仍能維持在對數級別(當節點數足夠大時,高度趨近於);[17]:413[2]:263但在最壞情況下,高度會達到節點數,查找性能退化至線性搜索的水平。[20]要保持二叉搜索樹的高效,關鍵在於通過「自平衡」機制,使樹的高度始終維持在級別。[9]:458–459[21]:50[17]:414[2]:263
若一棵樹的任意節點,其左右子樹高度之比都被某個常數所限制,就稱其為高度平衡樹。這一思想最早在AVL樹中使用,後續的紅黑樹也沿用了類似機制。[21]:50-51每次執行插入或刪除操作後,需要沿着從根到修改節點的路徑,檢查並修正各節點的高度,以維持平衡。[21]:52
在加權平衡樹中,平衡條件不再以高度衡量,而是以子樹的葉節點數量為準。葉節點數量即代表權重,左右子樹的權重差最多為常數。[21]:61[22]但單純依靠差值,難以在插入和刪除時用的代價維護,因此引入比例因子,要求左右子樹的權重各自至少占整棵子樹權重的比例,由此形成-權重平衡樹族。[21]:62
常見的自平衡二叉搜索樹包括:T樹[23]、樹堆[24]、紅黑樹[15]:273[1]:174、B樹[25]、2-3樹[9]:483、伸展樹[26]。
應用
二叉搜索樹可用於樹排序:先將所有元素插入二叉搜索樹中,然後對樹做中序遍歷,即可得到有序序列。[27]在快速排序的某些實現中,也可藉助二叉搜索樹來提高性能。[28]
二叉搜索樹也可用來實現優先隊列,藉助節點的鍵值來表示優先級。插入操作與普通的二叉搜索樹相同,但刪除操作取決於優先隊列的類型:[29]
- 升序優先隊列:移除最低優先級元素時,從根節點向左一路遍歷即可找到最小鍵。
- 降序優先隊列:移除最高優先級元素時,從根節點向右一路遍歷即可找到最大鍵。
參見
腳註
延伸閱讀
外部連結
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads