二叉搜索樹

二叉搜索樹（Binary Search Tree，簡稱BST）是一種特殊的二叉樹，它具有以下幾個特點：

1. 節點的左子樹上的所有節點的值都小于或等于該節點的值。
2. 節點的右子樹上的所有節點的值都大于或等于該節點的值。
3. 每個節點的左右子樹也都是二叉搜索樹。

這些特點使得二叉搜索樹在進行搜索、插入和刪除操作時非常高效。具體來說，在平均情況下，這些操作的時間復雜度都是 (O(\log n))，其中 (n) 是樹中的節點數。

二叉搜索樹的基本操作

1. 搜索（Search）：

   • 從根節點開始，比較目標值與當前節點的值：

     • 如果目標值等于當前節點的值，則搜索成功；

     • 如果目標值小于當前節點的值，則在左子樹中繼續搜索；

     • 如果目標值大于當前節點的值，則在右子樹中繼續搜索。

2. 插入（Insert）：

   • 從根節點開始，找到目標值應該插入的位置，保持二叉搜索樹的性質。
   • 如果目標值小于當前節點的值，則插入到左子樹中；
   • 如果目標值大于當前節點的值，則插入到右子樹中。

3. 刪除（Delete）：

   • 刪除操作稍微復雜一些，分為三種情況：
     1. 要刪除的節點是葉子節點（沒有子節點），直接刪除即可。
     2. 要刪除的節點有一個子節點，用該子節點替代要刪除的節點。
     3. 要刪除的節點有兩個子節點，需要找到該節點的中序后繼（右子樹中最小的節點）或中序前驅（左子樹中最大的節點），用這個節點的值替換要刪除的節點的值，然后刪除這個節點。

示例

假設我們有以下一組數據：[5, 3, 8, 2, 4, 7, 9]，構建的二叉搜索樹如下：

      5/ \3   8/ \ / \2  4 7  9

• 搜索 4：從根節點 5 開始，4 < 5，往左走；到達 3 節點，4 > 3，往右走；到達 4 節點，找到目標值。
• 插入 6：從根節點 5 開始，6 > 5，往右走；到達 8 節點，6 < 8，往左走；到達 7 節點，6 < 7，往左走，插入 6 節點。
• 刪除 3：節點 3 有兩個子節點，找到 4（中序后繼）替換 3，然后刪除節點 4。

二叉搜索樹因其高效的操作性能，在許多應用中被廣泛使用，如數據庫索引和內存中的數據結構。