热门问题
时间线
聊天
视角

二元搜尋樹

一種支援查詢等操作的二元樹 来自维基百科,自由的百科全书

二元搜尋樹
Remove ads

二叉搜索樹(英語:binary search tree,簡稱BST[a]是一種有根二叉樹數據結構。它要求每個內部節點的鍵值都大於其左子樹中所有節點的鍵值,且都小於其右子樹中所有節點的鍵值。該樹各項操作時間複雜度均與樹的高度成線性關係

事实速览 二叉搜索樹, 類型 ...
Remove ads
事实速览 「binary search tree」的各地常用譯名, 中國大陸 ...
Thumb
一棵二叉搜索樹,其節點數為9,高度為3,根節點為8

二叉搜索樹每次比較都能排除大約一半的剩餘節點,故能以對數時間查找、插入、刪除數據。但其性能依賴於節點的插入順序,插入隨機鍵值時仍能維持對數級別,但在最壞情況英語Best, worst and average case下會退化成鍊表。為保證效率,研究者發明了多種平衡樹,能將最壞查找複雜度維持在

二叉搜索樹最早由多位研究者獨立提出,1960年被用來解決帶標籤數據的存儲問題。其還可用來實現樹排序英語Tree sort優先隊列

Remove ads

歷史

二叉搜索樹最早由多位研究者獨立提出,包括P.F.溫德利、安德魯·唐納德·布思安德魯·科林托馬斯·N·希巴德[6][7]這種數據結構常被歸功於康威·柏納-李英語Conway Berners-Lee大衛·惠勒英語David Wheeler (computer scientist),他們在1960年將之用於磁帶帶標籤數據的存儲。[8]希巴德實現二叉搜索樹的方法也是最早廣為流傳的一種。[6]

若按任意順序插入節點,樹的高度可能接近節點數,導致操作效率急劇下降。研究者們發明了平衡樹(即能夠自平衡的二叉搜索樹),將樹的高度限制在以內。[9]:458–459同時,相關人員也提出了多種高度平衡的二叉搜索樹結構,例如AVL樹樹堆紅黑樹等。[10]其中,AVL樹是首類平衡樹,[11]格奧爾吉·阿傑爾松-韋利斯基葉夫根尼·蘭迪斯於1962年發明,用於高效組織信息。[12][13]

Remove ads

性質

二叉搜索樹為有二叉樹,其節點順序為嚴格全序關係,每個節點都滿足:左子樹上所有節點的鍵值都小於該節點,右子樹上所有節點的鍵值都大於該節點。這一結構保證可以在對數時間內定位任意鍵值[14]:298[15]:287[1]:161-162除查找外,其也常用於排序,但性能取決於節點的插入和刪除順序——在最壞情況英語Best, worst and average case下,連續操作可能使樹退化為類似單鍊表的結構,這時的查找複雜度與鍊表相同。[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表示子樹規模信息,即子樹中節點數量。

範圍查找

利用中序遍歷,可以實現範圍查找英語Range query (computer science),即查詢兩個給定值之間的元素數量。其偽代碼如下:[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

其中list是用來收集結果的列表(也可視作隊列)。上述過程將所有符合條件的值加入列表中,並跳過不可能含有目標值的子樹。

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

刪除

Thumb
二元搜尋樹刪除節點的過程

從樹中刪除某個節點時,需分三種情況處理:[15]:295-297[1]:166-167

  1. 是葉節點:直接用空指針替換即可。(如圖中(a))
  2. 僅有一個子節點:用的子節點替換。(如圖中(b)、(c))
  3. 有兩個子節點:用中序遍歷所得到的後繼或前驅代替。此處以後繼為例:
    1. 如果恰好是的右子節點:直接用取代的右子樹保持不變。(如圖中(d))
    2. 如果位於的右子樹內部:先用的右子節點替換,再用替代。(如圖中(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但在最壞情況英語Best, worst and average case下,高度會達到節點數,查找性能退化至線性搜索的水平。[20]要保持二叉搜索樹的高效,關鍵在於通過「自平衡」機制,使樹的高度始終維持在級別。[9]:458–459[21]:50[17]:414[2]:263

高度平衡樹

若一棵樹的任意節點,其左右子樹高度之比都被某個常數所限制,就稱其為高度平衡樹。這一思想最早在AVL樹中使用,後續的紅黑樹也沿用了類似機制。[21]:50-51每次執行插入或刪除操作後,需要沿着從根到修改節點的路徑,檢查並修正各節點的高度,以維持平衡。[21]:52

加權平衡樹

在加權平衡樹中,平衡條件不再以高度衡量,而是以子樹的葉節點數量為準。葉節點數量即代表權重,左右子樹的權重差最多為常數[21]:61[22]但單純依靠差值,難以在插入和刪除時用的代價維護,因此引入比例因子,要求左右子樹的權重各自至少占整棵子樹權重的比例,由此形成-權重平衡樹族。[21]:62

其他類型

常見的自平衡二叉搜索樹包括:T樹英語T-tree[23]樹堆[24]紅黑樹[15]:273[1]:174B樹[25]2-3樹[9]:483伸展樹[26]

應用

排序

二叉搜索樹可用於樹排序:先將所有元素插入二叉搜索樹中,然後對樹做中序遍歷,即可得到有序序列。[27]快速排序的某些實現中,也可藉助二叉搜索樹來提高性能。[28]

優先隊列

二叉搜索樹也可用來實現優先隊列,藉助節點的鍵值來表示優先級。插入操作與普通的二叉搜索樹相同,但刪除操作取決於優先隊列的類型:[29]

  • 升序優先隊列:移除最低優先級元素時,從根節點向左一路遍歷即可找到最小鍵。
  • 降序優先隊列:移除最高優先級元素時,從根節點向右一路遍歷即可找到最大鍵。

參見

腳註

延伸閱讀

外部連結

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads