二元搜尋樹

說明

在二元樹中插入及搜尋數字。

當我們需要表示已排序的資料時，陣列並不是一個好的資料結構。

假設我們有一個陣列[1, 3, 4, 5]，並在其中加入 2，讓它變成[1, 3, 4, 5, 2]。 現在我們得把整個陣列重新排序一次！ 我們可以改善這個做法：只要為新項目[1, nil, 3, 4, 5]騰出空間，再把項目放進新增的空間裡就行了。 但這仍然需要把許多元素往後位移一格。

不過，二元搜尋樹在處理已排序的資料時，效率要高得多。

二元搜尋樹由一連串相連的節點組成。 每個節點包含一筆資料（例如數字 3）、一個名為left的變數，以及一個名為right的變數。 left和right變數會指向nil或其他節點。 由於這些其他節點底下又接著其他節點，我們說 left 和 right 變數指向的是子樹。 左子樹中的所有資料都小於或等於目前節點的資料，而右子樹中的所有資料都大於目前節點的資料。

舉例來說，如果我們有一個包含資料 4 的節點，並加入資料 2，我們的樹會長這樣：

      4
     /
    2

如果我們接著加入 6，它會變成這樣：

      4
     / \
    2   6

如果我們接著加入 3，它會變成這樣

       4
     /   \
    2     6
     \
      3

而如果我們接著加入 1、5 和 7，它會變成這樣

          4
        /   \
       /     \
      2       6
     / \     / \
    1   3   5   7

致謝

這些圖片由 habere-et-dispertire 使用 Till Tantau 的 PGF/TikZ 製作。

實作

在 Cairo（或任何具有不可變記憶體的純函式語言）中，要實作一個既有效率又可修改的樹狀結構並不容易，因為這類語言的設計初衷，就是避免在資料建立之後再加以變更。 這種不可變性意味著，你無法直接更新樹狀結構裡的節點；每當你要修改它時，都必須建立一份新的樹。

為了說明為什麼會這樣，想像一個簡單的二元樹結構，其中每個節點都有一個左子節點和一個右子節點。 假設我們從這樣一棵小樹開始：

       1
      / \
     2   3

現在，假設我們想加入一個新節點 4，作為節點 2 的左子節點。 在純函式語言（例如 Cairo 或 Haskell）中，記憶體是不可變的，所以我們不能直接把節點 4 加到 2 上。 相反地，我們必須為從根節點到被修改節點這條路徑上的每一個節點都建立新版本，因為這條路徑上的每個節點現在都指向新的或修改過的子樹。

整個過程大致會像這樣：

1. 把節點 4 加到節點 2：

   • 為節點2建立一個新版本，它現在以4作為左子節點。

       2'
      / 
     4   
   

2. 更新根節點：

   • 由於節點1原本指向舊的2，我們建立一個新版本的根節點1'，它現在在左邊指向更新後的節點2'，並在右邊保留節點3。

       1'
      / \
     2'  3
   

於是，最後得到的樹會變成：

       1'
      / \
     2'  3
    /
   4

這棵新樹（1'）仍然和原本的樹很相似，只是路徑經過了更新。 重點在於，為了維持不可變性，我們必須重新建立這條路徑上的每一個節點（從1到2），因為既有的節點無法就地修改。 原本的樹仍然存在（例如，所有指向它原本根節點1的參照仍然使用它），而這棵新樹則代表修改後的狀態。

在大型的樹中，這種做法可能會變得代價高昂，因為每一次修改都必須重新建立從根節點到被更新節點的一整條節點路徑，即使實際上只有一小部分的樹被改動。