簡介

二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹，是一種重要的數據結構。

它有以下特性：

1. 若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值。
2. 若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值。

在一般情況下，查詢效率比鏈表結構要高。

性質

二叉排序樹（Binary Sort Tree）具有以下性質：

1. 它的左子樹上所有節點的值均小于它的根節點的值。
2. 它的右子樹上所有節點的值均大于它的根節點的值。
3. 它的左右子樹也分別為二叉排序樹。

此外，查找最小和最大元素在二叉排序樹中也是非常簡單的，從根節點一直往左走，直到無路可走就可以得到最小值；從根節點一直往右走，直到無路可走就可以得到最大值。在插入新元素時，可以從根節點開始，遇鍵值較大者就向左，遇鍵值較小者就向右，一直到末端，就是插入點。

分類

二叉排序樹包括以下幾種：

1. 滿二叉樹：在不增加樹的層數的前提下，無法在多添加一個節點的二叉樹就是滿二叉樹。
2. 完全二叉樹：如果只是刪除了滿二叉樹最底層最右邊的連續若干個節點，這樣形成的二叉樹就是完全二叉樹。
3. 二叉搜索樹：一種特殊的二叉樹，其左子樹上的所有節點的值均小于它的根節點的值，右子樹上的所有節點的值均大于它的根節點的值。
4. 平衡二叉樹：一種特殊的二叉搜索樹，其左右子樹的高度差的絕對值不超過1。

應用場景

二叉排序樹的應用場景包括但不限于：

1. 快速查找 ：二叉排序樹的特性使得查找特定元素變得非常高效。在二叉搜索樹中，每次比較后可以確定下一步是向左還是向右，這使得查找時間復雜度可以保持在O(log n)，其中n是樹中節點的數量。
2. 插入和刪除 ：二叉排序樹的插入和刪除操作也是高效的。當插入一個新的節點時，可以根據其值的大小來決定放在左子樹還是右子樹，或者在必要時進行調整以保持二叉排序樹的平衡。刪除節點時，也可以根據其位置和與相鄰節點的關系來決定如何刪除。
3. 平衡二叉樹的應用 ：平衡二叉樹如AVL樹、紅黑樹等，在實際應用中更為廣泛。例如紅黑樹被廣泛用于C++的STL中，如map和set的實現，還有Linux文件管理。AVL樹雖然應用相對較少，但windows對進程地址空間的管理用到了AVL樹。
4. 大數據查找 ：二叉排序樹非常適合處理大量數據，例如從10億數據里面找到前100大的數。通過構建一個最小堆，可以高效地找到最大的k個元素。
5. 字典樹（Trie） ：用在統計和排序大量字符串，如自動機、M數據庫索引。

總的來說，二叉排序樹是一種非常實用的數據結構，可以在許多場景下發揮重要作用。

時間復雜度

二叉排序樹的時間復雜度主要取決于樹的結構和操作類型。

對于查找操作，二叉排序樹在最壞的情況下（即完全二叉樹或接近完全二叉樹）下，時間復雜度為O(n)，其中n為樹中節點的數量。然而，在平均情況下，二叉排序樹的查找時間復雜度為O(log n)。

對于插入操作，在最壞的情況下（即樹接近滿二叉樹），插入的時間復雜度為O(n)。但在平均情況下，插入時間復雜度為O(log n)。

對于刪除操作，如果刪除的是葉子節點，時間復雜度為O(log n)。如果刪除的是內部節點，時間復雜度為O(log n)。如果刪除的是根節點，且樹有兩個子節點，則刪除操作時間復雜度為O(log n)。

示例

以下是一個簡單的Java示例，演示了如何使用二叉排序樹（Binary Search Tree）來存儲和搜索整數：

public class BinarySearchTree {class Node {int key;Node left, right;public Node(int item) {key = item;left = right = null;}}Node root;BinarySearchTree() {root = null;}void insert(int key) {root = insertRec(root, key);}Node insertRec(Node root, int key) {if (root == null) {root = new Node(key);return root;}if (key < root.key) {root.left = insertRec(root.left, key);} else if (key > root.key) {root.right = insertRec(root.right, key);} else { // Duplicate keys not allowedreturn root;}return root;}void inorder()  {inorderRec(root);}void inorderRec(Node root) {if (root != null) {inorderRec(root.left);System.out.println(root.key);inorderRec(root.right);}}public static void main(String[] args) {BinarySearchTree tree = new BinarySearchTree();tree.insert(8);tree.insert(3);tree.insert(10);tree.insert(1);tree.insert(6);tree.insert(14);tree.insert(4);tree.insert(7);tree.insert(13);// tree.delete(10); // uncomment this to see the impact of deletion from BSTtree.inorder(); } 
} 

在這個示例中，我們定義了一個二叉排序樹的節點，它有一個鍵（key）和兩個子節點（left 和 right）。樹中的每個節點都滿足二叉排序樹的性質：左子樹上的所有節點的鍵都小于當前節點的鍵，右子樹上的所有節點的鍵都大于當前節點的鍵。我們在 insert() 方法中使用遞歸方式插入新的節點，并保證樹的性質。inorder() 方法用于按中序遍歷順序打印樹中的所有元素。

拓展

AVL樹你需要了解一下

紅黑樹你需要了解一下

滿二叉樹你需要了解一下

完全二叉樹你需要了解一下

哈夫曼樹你需要了解一下