ADT Binary Search 二元搜尋樹

ADT（抽象資料型別，Abstract Data Type）中的二元搜尋樹（Binary Search Tree，簡稱BST）是一種樹狀結構的資料型別，在儲存和檢索有序資料時非常有效率。BST 是一種特殊的二元樹，其每個節點最多有兩個子節點，並且具有以下特性：

特性與結構

1. 節點的結構：

• 每個節點包含一個資料元素（鍵值）和最多兩個子節點（左子節點和右子節點）。
• 左子節點儲存的鍵值小於父節點的鍵值。
• 右子節點儲存的鍵值大於父節點的鍵值。

1. 基本操作：

• 搜尋（Search）：從根節點開始，如果要搜尋的值小於當前節點的值，則遞迴地向左子樹搜尋；如果大於當前節點的值，則向右子樹搜尋；如果相等，則找到目標值。
• 插入（Insert）：根據BST的特性，從根節點開始比較要插入的值和當前節點的值，直到找到適當的位置插入新節點。
• 刪除（Delete）：刪除操作較為複雜，需考慮以下幾種情況：
  1. 要刪除的節點是葉子節點（無子節點）：直接刪除該節點。
  2. 要刪除的節點只有一個子節點：用該子節點替換要刪除的節點。
  3. 要刪除的節點有兩個子節點：找到右子樹中最小的節點（或左子樹中最大的節點）來替換該節點的值，然後刪除該最小（或最大）的節點。

1. 遍歷（Traversal）：

• 中序遍歷（In-order Traversal）：先遍歷左子樹，再訪問根節點，最後遍歷右子樹。中序遍歷的結果是一個按升序排列的序列。
• 前序遍歷（Pre-order Traversal）：先訪問根節點，然後遍歷左子樹，最後遍歷右子樹。
• 後序遍歷（Post-order Traversal）：先遍歷左子樹，然後遍歷右子樹，最後訪問根節點。

性能

在理想情況下（即樹是平衡的），BST的搜尋、插入和刪除操作的平均時間複雜度為O(log n)。然而，在最壞的情況下（例如，插入順序導致樹退化為鏈表），這些操作的時間複雜度可能退化為O(n)。

應用

二元搜尋樹廣泛應用於各種需要高效搜尋和排序的資料結構和演算法中，例如：

• 資料庫索引：BST 可以作為某些資料庫系統中用於快速資料檢索的基礎資料結構。
• 集合和字典：用來實作有序集合和字典。
• 優先佇列：在某些情況下，可以使用BST來實作優先佇列。

平衡二元搜尋樹

為了避免BST退化為鏈表，通常使用平衡二元搜尋樹（如AVL樹、紅黑樹）來確保樹的平衡性，從而保證操作的時間複雜度接近O(log n)。