Lesson 0405 · 二叉搜索树 BST

④ 数据结构与算法 — 第 5 课

1. BST 的规则

二叉搜索树（Binary Search Tree，BST）满足：

• 左子树所有节点的值 < 根的值
• 右子树所有节点的值 > 根的值
• 左右子树本身也分别是 BST

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

看根 8：左边所有数都比 8 小，右边所有数都比 8 大。每个子树也满足这个规则。注意是整棵子树都满足，不只是直接孩子——比如 7 比 3 大，但它在 3 的右子树里，依然小于 8。

2. 查找：每次砍掉一半

想找 7：

• 7 < 8，去左子树
• 7 > 3，去右子树
• 7 > 6，去右子树
• 找到 7

bool search(Node* root, int x) {
    if (root == nullptr) return false;   // 走到空，没找到
    if (root->val == x) return true;     // 找到

    if (x < root->val) return search(root->left, x);
    else               return search(root->right, x);
}

每次只往一边走，理想情况下树比较平衡，高度约为 log n，所以查找是 O(log n)。这里的「砍掉一半」不是真删，而是每比较一次就排除掉一整棵子树。

3. 插入：找到空位放进去

Node* insert(Node* root, int x) {
    if (root == nullptr) {
        return new Node(x);              // 空位：新节点放这里
    }

    if (x < root->val) {
        root->left = insert(root->left, x);
    } else if (x > root->val) {
        root->right = insert(root->right, x);
    }
    // x == root->val 时这里什么都没做，表示不插入重复值

    return root;
}

插入 5 到上面的树：5 < 8 往左 → 5 > 3 往右 → 5 < 6 往左 → 5 > 4 往右 → 空位，插入。

注意 root->left = insert(root->left, x); 这个赋值：递归返回的可能是新节点，必须接回父节点，否则新节点就丢了。

4. 中序遍历 = 从小到大

BST 最重要的性质：中序遍历的结果一定有序。

void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

上面那棵树中序输出：

1 3 4 6 7 8 10 13 14

这也是为什么 set 遍历出来是有序的——它内部就是平衡 BST。

把同一棵 BST 的四种遍历按「第几个被访问」排开（表头 1–9 是访问次序，不是节点编号）：

看第二行：中序就是严格递增的 1 3 4 6 7 8 10 13 14。前序第一个是根 8，后序最后一个是根 8，层序按 8 → 3、10 → 1、6、14 → 4、7、13 一层层铺开。四种顺序，同一棵树，数字一个不差。

5. 删除：分三种情况

Node* findMin(Node* root) {
    while (root != nullptr && root->left != nullptr) {
        root = root->left;
    }
    return root;
}

Node* remove(Node* root, int x) {
    if (root == nullptr) return nullptr;

    if (x < root->val) {
        root->left = remove(root->left, x);
    } else if (x > root->val) {
        root->right = remove(root->right, x);
    } else {
        // 找到要删的节点
        if (root->left == nullptr) {
            Node* rightChild = root->right;
            delete root;
            return rightChild;
        }
        if (root->right == nullptr) {
            Node* leftChild = root->left;
            delete root;
            return leftChild;
        }

        // 有两个孩子：找右子树最小值（后继）
        Node* successor = findMin(root->right);
        root->val = successor->val;
        root->right = remove(root->right, successor->val);
    }

    return root;
}

拿删 8 走一遍：8 有两个孩子，右子树最小值是 10（10 没有左孩子），把 10 写到根的位置；然后到右子树里删掉原来那个 10，此时 10 只有一个右孩子 14，直接让 14 顶上来。整棵树仍然满足「左小右大」。

6. BST 的复杂度与退化

如果你按 1 2 3 4 5 顺序插入，BST 会一路往右，退化成链表：

1
 \
  2
   \
    3
     \
      4

所以真正好用的 BST 需要「平衡」，例如 AVL 树、红黑树。C++ 的 set、map 底层通常就是红黑树。

7. 完整示例

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// ==== 插入 ====
Node* insert(Node* root, int x) {
    if (root == nullptr) return new Node(x);
    if (x < root->val) root->left = insert(root->left, x);
    else if (x > root->val) root->right = insert(root->right, x);
    return root;
}

// ==== 查找 ====
bool search(Node* root, int x) {
    if (root == nullptr) return false;
    if (root->val == x) return true;
    if (x < root->val) return search(root->left, x);
    return search(root->right, x);
}

// ==== 中序遍历 ====
void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

// ==== main ====
int main() {
    Node* root = nullptr;
    int a[] = {8, 3, 10, 1, 6, 14, 4, 7, 13};

    for (int x : a) root = insert(root, x);

    inorder(root);  cout << endl;     // 1 3 4 6 7 8 10 13 14
    cout << search(root, 7) << endl;  // 1
    cout << search(root, 9) << endl;  // 0

    return 0;
}

8. 坑点清单

• 插入重复值被悄悄丢掉：x == root->val 时两条分支都不走，值就没了；要按题目决定允许还是拒绝重复。
• 删除两个孩子只改了 val：忘了去右子树删掉后继节点，树里会多出一个重复值，还漏了 delete。
• delete root 之后还读 root->left：必须先存孩子指针，再释放自己。
• 把「左小右大」只理解成直接孩子：规则管的是整棵子树，验证时要从根一路看下去。
• 按有序数据插入：树退化成链表，O(log n) 变 O(n)。
• 递归返回值没接住：root->left = insert(...) 漏了赋值，新节点就丢了。

9. 小测

10. 动手练习

11. 本课小结

• BST：左小右大，左右子树也是 BST（整棵子树，不只是直接孩子）。
• 查找：每次往一边走，平衡时 O(log n)，退化时 O(n)。
• 中序遍历：结果从小到大，这是 BST 最好用的性质。
• 删除：叶子直接删；一个孩子顶替；两个孩子用后继（右子树最小值）顶替。
• 退化与平衡：有序插入会变链表，所以 STL 用平衡树实现 set / map。