申論題

• 對於節點10，左子樹包含的節點值（3, 5, 7）均小於10，右子樹包含的節點值（12, 15, 18）均大於10。
• 對於節點5，其左子樹包含的節點值（3）小於5，右子樹包含的節點值（7）大於5。
• 以此類推，整棵樹滿足二元搜尋樹的定義。

總結

二元搜尋樹（BST）是一種高效的數據結構，用於存儲和檢索有序數據。它具有靈活性和高效性的優點，特別適合於需要頻繁查找、插入和刪除操作的應用場景。通過保持樹的平衡性，可以確保操作的高效性。

二元搜尋樹（Binary Search Tree，BST）是一種特殊的二元樹數據結構，用於高效地存儲和檢索數據。每個節點最多有兩個子節點，並且節點的值遵循特定的順序。以下是二元搜尋樹的定義及其特性：

定義

一棵二元搜尋樹具有以下特性：

1. 節點結構：

   • 每個節點包含一個值（關鍵字）、一個左子節點和一個右子節點。
   • 每個節點至多有兩個子節點，即左子節點和右子節點。

2. 節點排序：

   • 對於每個節點 NNN，其左子樹中的所有節點值都小於 NNN 的值。
   • 對於每個節點 NNN，其右子樹中的所有節點值都大於 NNN 的值。

特性

1. 有序性：

   • 二元搜尋樹中的節點值是有序的，這使得在樹中進行查找、插入和刪除操作變得高效。
   • 進行中序遍歷（In-order Traversal）時，會得到一個遞增排序的數列。

2. 查找效率：

   • 在理想情況下（二元搜尋樹是平衡的），查找、插入和刪除操作的時間複雜度是 O(log⁡n)O(\log n)O(logn)，其中 nnn 是樹中的節點數量。
   • 在最壞情況下（二元搜尋樹退化成鏈表），這些操作的時間複雜度是 O(n)O(n)O(n)。

3. 動態性：

   • 二元搜尋樹是一種動態數據結構，可以隨時進行插入和刪除操作，適用於動態集合的維護。

操作

1. 查找（Search）：

   • 從根節點開始，根據當前節點的值與目標值的比較結果決定下一步是向左子樹還是向右子樹查找，直到找到目標值或遍歷完整棵樹。

2. 插入（Insert）：

   • 從根節點開始，找到適當的插入位置，使插入後仍然保持二元搜尋樹的特性。

3. 刪除（Delete）：

   • 刪除節點後，需要重組樹結構，以保持二元搜尋樹的特性。
   • 根據被刪節點的子節點情況，重組方式有所不同：無子節點、有一個子節點、或有兩個子節點。