# BST 二元搜尋樹
###### tags: `資料結構` `排序法`
### 定義
* 可以是空的
* 每一個節點含有uniqlo key
* 左子樹的節點小於父節點
* 右子樹的節點大於父節點

---
### Search
1. 從 root 開始，先與 root 比較
2. 若比 root **小**就搜尋**左子樹**
3. 若比 root **大**就搜尋**右子樹**
4. **遞迴**直到找到或者已經沒有子樹可以尋找

public Node search(Node root, int key) 
{ 
    //若root是空的或root的值==key 
    if (root==null || root.key==key){
        return root;
    }
    
    //key大於root.key
    if (root.key < key){
        return search(root.right, key); 
    }
    
    //key小於root.key
    return search(root.left, key); 
} 

---
### Insert
1. 依大小插入節點在適當的位置
2. 從 root 尋訪
3. 同 search，比 root **小**就往**左子樹**找
4. 比 root **大**就往**右子樹**找
5. 遞迴做法：`root.left = insertRec(root.left, key);`
6. 若此時是一個**空節點**，就建立要插入的節點並**回傳節點(對應第五點)**

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); 
  
    return root; 
} 

---
### Detele
1. 若比 root.key **小**，遞迴刪除 **root.left** 並回傳
2. 若比 root.key **大**，遞迴刪除 **root.right** 並回傳
3. 若要刪除的是root
1. 若沒有兒子節點直接刪除並回傳null
2. 若只有一個兒子樹直接回傳兒子節點 (為新的root)
3. 若有兩個兒子樹
* 找**左子樹**的最**大**值 或
* 找**右子樹**的最**小**值 以下程式取此選項
* 設 `root.key = minValue(root.right)`
* 將該最**小**值的節點刪除並回傳**新的 root.right**
* `root.right = deleteRec(root.right, root.key);`

Node deleteRec(Node root, int key)
    {
        if (root == null)
            return root;
 
        if (key < root.key)
            root.left = deleteRec(root.left, key);
        else if (key > root.key)
            root.right = deleteRec(root.right, key);
        else {
            
            if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;
            
            root.key = minValue(root.right);    //把新的值放入
            root.right = deleteRec(root.right, root.key);  
            //刪掉已成為新的root的值，存回root.right
        }
        return root;
    }

---
### 複雜度
**搜尋 & 插入**時間複雜度
average = O(logn)，若是平衡BST
worst case = O(n)，chain BST (skewed)

---
## Tree Sort
### 概念
以 **BST** 來實作排序，再用 **inorder** 方式尋訪即可得到排序好的結果

### 步驟
1. 用**插入**方式來建立BST
2. **inorder** traversal

### 複雜度
* best case = average case = **O(nlogn)**
* worst case = **O(n*n)(左傾數、右傾數)**

---
參考資料：**GeeksforGeeks** website and **WilliamFiset** youtube channel