二元搜尋樹

3.1 二元搜尋樹 (BST) 的定義

二元搜尋樹 (BST) 是一種具有以下特性的二元樹：

• 對於任何節點，其左子樹的節點只包含鍵值小於該節點的節點。
• 對於任何節點，其右子樹的節點只包含鍵值大於該節點的節點。
• 每個節點的兩個子樹也是二元搜尋樹。

BST 的例子：

BST 是 Binary Search Tree 的縮寫，也就是「二元搜尋樹」的意思。其實這是一種透過「樹」的形式來組織數據，可以非常快速地進行搜尋。樹的結構實際上是一種隱藏/巧妙的元素排序。

中序遍歷 (in-order traversal)

遍歷的目標 是以特定方式形成節點的列表（或節點中數據，這在術語和實際應用中很重要）。中序遍歷是指樹的根節點在左子樹和右子樹遍歷結果之間。

結合二元搜尋樹的特性（不等式，見理論），中序遍歷會形成一個排序好的節點列表 — 太厲害了！下面是之前定義的樹的遍歷樣子：

3.2 BST 的工作原理和特性

工作原理：

• 數據組織：BST 組織數據以便提供高效的搜尋、插入和刪除元素。
• 遞迴結構：BST 中的每個節點遵循同樣的規則，這使得結構具有遞迴性。
• 平衡性：為了確保最佳性能，BST 應該是平衡的，即左子樹和右子樹的高度應該大致相同。

BST 的特性：

• 有序性： 隨時可以以 "in-order" 的順序遍歷樹 （左子樹 → 當前節點 → 右子樹），以獲得所有元素的排序順序。
• 操作時間：
  • 平均來說，搜尋、插入和刪除操作的時間是 O(log n)，其中 n 是節點數量。
  • 最糟情況下（如果樹不平衡）操作時間可能達到 O(n)。
• 唯一鍵值：BST 中的所有鍵值必須是唯一的，以保持有序性。

3.3 主要操作

1. 插入 (Insertion)：

操作原理：

• 從根節點開始。
• 將新節點的鍵與當前節點的鍵進行比較。
• 如果新鍵較小，則移至左子樹；如果較大，則移至右子樹。
• 重複該過程直到找到適合插入新節點的位置（即左或右子節點不存在）。

算法：

1. 如果樹是空的，新節點成為根節點。
2. 否則，遞迴地找到正確位置並添加新節點。

2. 刪除 (Deletion)：

操作原理：

• 找到要刪除的節點。
• 考慮三種情況：
• 節點是葉子節點（沒有子節點）：直接刪除節點。
• 節點只有一個子節點：用它的子節點替代該節點。
• 節點有兩個子節點：找到右子樹中的最小節點（或左子樹中最大的），複製其值到刪除節點並遞迴地刪除右子樹中的最小節點。

算法：

1. 找到具有指定鍵的節點。
2. 根據情況執行相應的刪除和節點重新分配。

3. 搜尋 (Search)：

操作原理：

• 從根節點開始。
• 將目標節點的鍵與當前節點的鍵進行比較。
• 如果鍵相同，返回該節點。
• 如果鍵較小，則移至左子樹；如果較大，則移至右子樹。
• 重複該過程直到找到具有目標鍵的節點或達到樹的末端（在這種情況下，節點未找到）。

算法：

1. 如果樹是空的或鍵與節點的鍵相同，返回該節點。
2. 如果目標節點的鍵較小，遞迴搜尋左子樹。
3. 如果目標節點的鍵較大，遞迴搜尋右子樹。

3.4 使用 BST 解決的示例問題

1. 在動態集合中查找元素

需要維護一個數字集合，可以添加新的元素，刪除現有元素，並快速查找指定數字是否在集合中。

使用 BST 的解決方案：

• 將新元素插入樹中。
• 刪除現有元素。
• 在樹中查找元素。

使用示例：

在系統中維護用戶注冊列表，用戶可以被添加和刪除，系統必須快速檢查用戶是否已注冊。

2. 找到最小和最大元素

需要快速找到數據集中最小和最大值。

使用 BST 的解決方案：

• 最小元素位於樹的最左節點。
• 最大元素位於樹的最右節點。

使用示例：

支持股票價格跟踪系統，需要快速找到當前時刻的最低和最高價格。

3. 檢查表達式的平衡

給定一個數學表達式，需要檢查其括號的開閉平衡。

使用 BST 的解決方案：

使用 BST 儲存中間狀態以檢查括號的平衡。

使用示例：

解析和編譯代碼，需要檢查表達式中括號的正確放置。

4. 構建詞典

需要創建一個數據結構來存儲詞典，其中的單詞可以被添加、刪除並快速查找。

使用 BST 的解決方案：

• 按字母順序將單詞添加到樹中。
• 按照鍵值搜尋單詞。

使用示例：

文本自動更正系統，需要快速找到和更正單詞。