在Day24有提到inorder可以來驗證是否Binary Search Tree，我們來介紹下二元搜尋樹Binary Search Tree。

二元搜尋樹(Binary Search Tree, BST)定義

1. 左子樹所有值<父節點的值

2. 父節點的值<右子樹所有值

時間複雜度

1. 平衡時：O(log n)

2. 最壞情況：全部在同一邊變成單向linkedlist O(n)

空間複雜度

1. 遞迴下去找時只要樹高O(h)，平衡時O(logn)，最壞O(n)

BST 插入 (Insertion)

1. 從根開始比較：

   • 比當前節點小 → 去左子樹

   • 比當前節點大 → 去右子樹

2. 找到空位插入

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
struct Node {
    val: i32,
    left: Option<Rc<RefCell<Node>>>,
    right: Option<Rc<RefCell<Node>>>,
}

impl Node {
    // 建立新節點（Rc + RefCell）
    fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            key,
            left: None,
            right: None,
        }))
    }
}


// BST 插入：將 key 插入以 root 為根的子樹
fn insert(root: &mut Option<Rc<RefCell<Node>>>, key: i32) {
    match root {
        None => {
            // 目前是空子樹，直接放新節點
            *root = Some(Node::new(key));
        }
        Some(rc_node) => {
            // 可變借用節點內容
            let mut node = rc_node.borrow_mut();
            if key < node.key {
                insert(&mut node.left, key);
            } else {
                insert(&mut node.right, key);
            }
        }
    }
}

fn main() {
    // 插入建立一棵 BST
    let mut root: Option<Rc<RefCell<Node>>> = None;
    for k in [8, 3, 10, 1, 6, 14, 4, 7, 13] {
        insert(&mut root, k);
    }
}

BST 搜尋 (Search)

1. 從根開始比較：

   • 比當前節點小 → 去左子樹

   • 比當前節點大 → 去右子樹

2. 找到值回傳 or 沒找到回傳 None

fn search(root: &Option<Rc<RefCell<Node>>>, key: i32) -> Option<Rc<RefCell<Node>>> {
    let mut cur = root.clone();
    while let Some(rc_node) = cur {
        // 暫時不可變借用，查 key 與分支
        let node_ref = rc_node.borrow();
        if key == node_ref.key {
            // 找到了，回傳這個 Rc 的 clone
            return Some(rc_node.clone());
        } else if key < node_ref.key {
            cur = node_ref.left.clone();
        } else {
            cur = node_ref.right.clone();
        }
        // node_ref 在這一輪結束就釋放，避免持有借用太久
    }
    None
}

BST 刪除 (Deletion)

刪除節點分三種情況：

1. 葉子節點 → 直接刪除

2. 只有一個子樹 → 讓子樹接上父節點

3. 有兩個子樹 → 找右子樹最小值或左子樹最大值來替代

fn delete(root: &mut Option<Rc<RefCell<Node>>>, val: i32) {
    // 如果空樹，直接返回
    let Some(rc)=root.clone() else { return };
    let mut n = rc.borrow_mut();
    
    // 二分法往下找
    if n.val < val {
        delete(&mut n.right,val);
        return
    } else if n.val>val {
        delete(&mut n.left,val);
        return
    
    }
    
    match (n.left.clone(),n.right.clone()) {
        (None,None) => {
            *root=None;
        },
        (Some(st),None)|(None,Some(st)) => {
            *root=Some(st);
        },
        (Some(l_st),Some(r_st)) => {
        
            let min=min_val(&n.right).expect("rigt subtree must have node");
            n.val = min;
            delete(&mut n.right,min);
        }
    }
}

找右子樹最小的取代刪掉的節點

fn min_val(root: &Option<Rc<RefCell<Node>>>) -> Option<i32> {
    let mut cur = root.clone();
    while let Some(rc) = cur {
        let n = rc.borrow();
        if n.left.is_none() {
            return Some(n.val);
        }
        cur = n.left.clone();
    }
    None
}

Day25 總結

1. 二元樹中序遍歷的值是由小到大即為二元搜尋樹(BST)
2. BST插入會放在遍歷到最後的葉節點
3. BST刪除節點操作需考慮三種情況

參考資料

1. search binary tree
2. insert binary tree
3. delete binary tree