二元搜尋樹

說明

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

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

假設我們有一個陣列[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 製作。