二元搜尋樹（Binary Search Tree，簡稱BST）是一種特殊的二元樹，它具有以下性質：
每個節點都有一個鍵（或稱為「值」）和兩個指向子節點的參照。
每個節點的鍵都必須大於左子樹中任何節點的鍵，並且小於右子樹中任何節點的鍵。
每個子樹也都是一個二元搜尋樹。
不允許鍵值相等的節點（或者可以將規則定為相等的值僅存於某一特定方向的子樹中）。
舉例而言，下面這棵樹就是一個二元搜尋樹：
markdown
Copy code
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
在這個樹中，根節點是8，所有左子樹的節點值（3、1、6、4、7）都小於8，所有右子樹的節點值（10、14、13）都大於8。此外，6的左子樹節點值（4）小於6，右子樹節點值（7）大於6，以此類推。
使用二元搜尋樹進行資料排序的一種方法是進行中序遍歷（In-order Traversal）。中序遍歷的過程是先遍歷左子樹，然後訪問根節點，最後遍歷右子樹。若對上面的二元搜尋樹進行中序遍歷，訪問節點的順序將是：
1, 3, 4, 6, 7, 8, 10, 13, 14
這正是節點值的升序排列。
時間複雜度和記憶器空間複雜度如下：
時間複雜度：在平衡的二元搜尋樹中，插入和搜尋的操作平均時間複雜度是O(log n)，其中n是樹中節點的數量。但是，在最壞的情況下（樹退化成線性結構），這些操作的時間複雜度會變成O(n)。因此，對二元搜尋樹進行排序的平均時間複雜度是O(n log n)，但最壞情況是O(n^2)。
記憶器空間複雜度：對於二元搜尋樹的每一個節點，你需要存儲其值和兩個指針（分別指向左右子樹）。所以整個樹的空間複雜度是O(n)。
為了保持二元搜尋樹的性能，經常需要進行樹的平衡（如AVL樹或紅黑樹），以確保樹的高度盡可能低，保持操作的時間複雜度接近於O(log n)。
阿摩線上測驗
登入