Chapter 7: 二叉搜索树

我们已经在第五章介绍了树。这一章我们将目光聚集到二叉搜索树上。

还记得二分搜索的缺点嘛？二分搜索需要在一个排好序的数组上才能使用，而且正如我们之前所说，二分搜索在这种情况下适用于静态数据的搜索，因为一旦我们需要在数组里添加或删除元素，你需要花费$O(n)$来调整其他元素的位置。

使用二叉搜索树就是我们的对策！二叉搜索树允许我们同样使用二分搜索，同时我们也不需要因为一个元素的添加或者删除来花费$O(n)$移动整个数据结构。

二叉搜索树

二叉搜索树 (Binary Search Tree, BST) 是一种特殊的二叉树，它满足以下性质：

左子树中所有节点的值 < 根节点的值
右子树中所有节点的值 > 根节点的值
左右子树也都是二叉搜索树（递归定义）

⚠ 常见误区

注意是"所有节点"而不是"左/右子节点"！下面这棵树不是 BST：

    10
   /  \
  5    15
 / \
3   12   ← 12 > 10，违反了"左子树所有节点 < 根"

这个性质使得 BST 非常适合用于查找操作——我们可以像二分搜索一样，每次排除一半的数据。

在实现BST的时候，与普通树不同，我们会存储这些信息：

key：当前节点的值
left：指向左子节点的指针
right：指向右子节点的指针
parent：指向父节点，方便我们回溯。这个是可选项。

struct Node {
    int key;
    Node* left;
    Node* right;
    Node* parent; // 可选
};

BST 的核心性质

BST 的中序遍历结果一定是升序排列的！ 这是 BST 最重要的性质之一。

例如对下面的 BST 进行中序遍历：

    8
   / \
  3   10
 / \    \
1   6    14

对它的中序遍历结果就是：1, 3, 6, 8, 10, 14

这个性质可以用来：

验证一棵树是否是 BST
找第 k 小的元素
将 BST 转换为有序数组

BST的性能取决于它的高度(h)。在一个完全平衡的二叉树内$h \approx \log(n)$，相反，如果一个二叉树本质上就是一个链表形态，那么$h \approx n$。

BST 的查找

TreeNode* search(TreeNode *node, int key) {
    if (node == NULL || node->data == key)
        return node;
    if (key < node->data)
        return search(node->left, key);
    else
        return search(node->right, key);
}

每次比较后，搜索范围缩小一半，时间复杂度为 $O(h)$，其中 $h$ 是树的高度。

寻找BST中的最值

由于BST的特性，最小值一定在最左边，最大值一定在最右边。所以我们只需要一直往左（或往右）走到底就行了。

// 找最小值：一直往左
TreeNode* findMin(TreeNode *node) {
    if (node == NULL) return NULL;
    while (node->left != NULL)
        node = node->left;
    return node;
}

// 找最大值：一直往右
TreeNode* findMax(TreeNode *node) {
    if (node == NULL) return NULL;
    while (node->right != NULL)
        node = node->right;
    return node;
}

时间复杂度：$O(h)$

后继节点与前驱节点

在二叉搜索树中：

后继节点 (Successor)：比 x 大的最小节点（中序遍历中 x 的下一个）
前驱节点 (Predecessor)：比 x 小的最大节点（中序遍历中 x 的上一个）

例如在序列 10, 15, 20 中，15 的后继是 20，前驱是 10。

寻找后继节点

分两种情况：

情况1：节点有右子树

后继就是右子树中的最小值。为什么？因为右子树里所有值都比当前节点大，而我们要的是"大的里面最小的那个"。

找 15 的后继：
      15
        \
        20    ← 进入右子树
       /
      18      ← 然后一直往左走到底
     /
    17        ← 后继

情况2：节点没有右子树

后继在父节点中。我们需要往上回溯，直到找到一个"我是它左子节点"的父节点，那么这个节点就是后继。

找 13 的后继：
        15         ← 13 是 15 的左子树中的节点，15 就是后继
       /
      10
        \
        13    ← 没有右子树，往上找

就好比如果我是父节点的右子节点，说明父节点比我小，不是后继，继续往上；如果我是父节点的左孩子，说明父节点比我大，就是后继。

TreeNode* successor(TreeNode *root, TreeNode *node) {
    // 情况1：有右子树，找右子树的最小值
    if (node->right != NULL)
        return findMin(node->right);
    
    // 情况2：没有右子树，往上找
    TreeNode *succ = NULL;
    while (root != NULL) {
        if (node->data < root->data) {
            succ = root;  // root 可能是后继，记录下来
            root = root->left;
        } else if (node->data > root->data) {
            root = root->right;
        } else {
            break;  // bro找到node了
        }
    }
    return succ;
}

寻找前驱节点（对称操作）

有左子树：前驱是左子树的最大值
没有左子树：往上找，直到"我是它右孩子"的祖先

TreeNode* predecessor(TreeNode *root, TreeNode *node) {
    if (node->left != NULL)
        return findMax(node->left);
    
    TreeNode *pred = NULL;
    while (root != NULL) {
        if (node->data > root->data) {
            pred = root;
            root = root->right;
        } else if (node->data < root->data) {
            root = root->left;
        } else {
            break;
        }
    }
    return pred;
}

BST 的插入

插入操作遵循查找的路径，找到合适的空位置插入新节点：

TreeNode* insert(TreeNode *node, int key) {
    if (node == NULL) {
        // 创建新节点
        TreeNode *newNode = malloc(sizeof(TreeNode));
        newNode->data = key;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    if (key < node->data)
        node->left = insert(node->left, key);
    else if (key > node->data)
        node->right = insert(node->right, key);
    // 如果 key == node->data，通常忽略（不允许重复值）
    return node;
}

插入过程就像在做一次失败的查找——沿着查找路径走到底，遇到 NULL 的位置就是新节点应该待的地方。

要注意BST 中新插入的节点一定是叶子节点！ 我们永远不会在树的中间插入。

插入顺序对树形的影响

同样的数据，不同的插入顺序会产生完全不同的树形：

按顺序插入 1, 2, 3, 4, 5：       随机插入 3, 1, 4, 2, 5：
1                                       3
 \                                     / \
  2                                   1   4
   \                                   \   \
    3                                   2   5
     \
      4                             高度 = 3（平衡）
       \
        5
高度 = 5（退化成链表）

这就是为什么随机插入平均能得到 $O(\log n)$ 的高度，而有序插入会导致 $O(n)$ 的最坏情况。

BST 的删除

删除操作是 BST 中最复杂的操作，需要分三种情况讨论：

情况1：删除叶子节点

直接删除，将父节点指向它的指针改为 NULL。

删除 4：
    5           5
   / \    →    /
  3   7       3   7
 /
4

情况2：删除只有一个子节点的节点

用它唯一的子节点来替代自己。

删除 3（只有左子节点）：
    5           5
   / \    →    / \
  3   7       2   7
 /
2

情况3：删除有两个子节点的节点

这种情况比较复杂。我们不能简单替换，否则会破坏BST的性质。

在这种情况下我们采用这样的流程：

找到该节点的中序后继 (In-Order Successor)（右子树的最小值）或中序前驱 (In-Order Predecessor)（左子树的最大值）
用后继/前驱的值替换要删除节点的值
然后删除那个后继/前驱节点（它最多只有一个子节点，回到情况1或2）

删除 5（有两个子节点）：
      5                 6
     / \               / \
    3   8      →      3   8
       /                 /
      6                 7
       \
        7

步骤：找到后继 6 → 用 6 替换 5 → 删除原来的 6（情况2）

⚠注意

找中序后继：进入右子树，然后一直往左走到底
找中序前驱：进入左子树，然后一直往右走到底

TreeNode* deleteNode(TreeNode *node, int key) {
    if (node == NULL) return NULL;
    
    // 先找到要删除的节点
    if (key < node->data) {
        node->left = deleteNode(node->left, key);
    } else if (key > node->data) {
        node->right = deleteNode(node->right, key);
    } else {        
        // 情况1 & 2：没有子节点或只有一个子节点
        if (node->left == NULL) {
            TreeNode *temp = node->right;
            free(node);
            return temp;
        } else if (node->right == NULL) {
            TreeNode *temp = node->left;
            free(node);
            return temp;
        }
        
        // 情况3：有两个子节点
        // 找右子树的最小值（中序后继）
        TreeNode *successor = findMin(node->right);
        // 用后继的值替换当前节点的值
        node->data = successor->data;
        // 删除后继节点
        node->right = deleteNode(node->right, successor->data);
    }
    return node;
}

为什么用后继/前驱替换是安全的？

以后继为例：

后继是右子树中的最小值，所以它比左子树所有节点都大
后继在右子树中，所以它比原节点小的所有节点都在左边
后继是右子树最小的，所以原右子树其他节点都比它大

替换后，BST 性质还能够完美保持。

😋😋😋

删除操作的一个小坑

如果总是用后继节点替换，树会逐渐向左倾斜；如果总是用前驱节点替换，树会逐渐向右倾斜。

一个改进方案是随机选择用后继还是前驱，或者交替使用，以保持树的平衡性。

BST 的性能分析

操作	平均情况	最坏情况
查找	$O(\log n)$	$O(n)$
插入	$O(\log n)$	$O(n)$
删除	$O(\log n)$	$O(n)$
找最值	$O(\log n)$	$O(n)$
找后继/前驱	$O(\log n)$	$O(n)$

最坏情况发生在树退化为链表的时候（例如按顺序插入 1, 2, 3, 4, 5...）。这就是为什么我们需要平衡二叉树（如 AVL 树、红黑树）。相关的内容会在下一章还是两章讲解。

BST 的常见应用

1. 验证一棵树是否是 BST

利用中序遍历的有序性：

// 方法1：中序遍历，检查是否升序
int prev = INT_MIN;
bool isValidBST(TreeNode *node) {
    if (node == NULL) return true;
    
    if (!isValidBST(node->left)) return false;
    
    if (node->data <= prev) return false;  // 注意：要用 <= 排除相等
    prev = node->data;
    
    return isValidBST(node->right);
}

方法2：递归检查范围

bool isValidBSTHelper(TreeNode *node, int min, int max) {
    if (node == NULL) return true;
    if (node->data <= min || node->data >= max) return false;
    return isValidBSTHelper(node->left, min, node->data) &&
           isValidBSTHelper(node->right, node->data, max);
}

bool isValidBST(TreeNode *root) {
    return isValidBSTHelper(root, INT_MIN, INT_MAX);
}

2. 找第 k 小的元素

中序遍历到第 k 个就停：

int kthSmallest(TreeNode *root, int k) {
    int count = 0;
    int result = 0;
    inorderKth(root, k, &count, &result);
    return result;
}

void inorderKth(TreeNode *node, int k, int *count, int *result) {
    if (node == NULL || *count >= k) return;
    
    inorderKth(node->left, k, count, result);
    
    (*count)++;
    if (*count == k) {
        *result = node->data;
        return;
    }
    
    inorderKth(node->right, k, count, result);
}

3. 找两个节点的最近公共祖先 (Least Common Ancestor)

BST 的 LCA 比普通二叉树简单得多：

TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (p->data < root->data && q->data < root->data)
        return lowestCommonAncestor(root->left, p, q);
    if (p->data > root->data && q->data > root->data)
        return lowestCommonAncestor(root->right, p, q);
    // p 和 q 分别在两侧，或者其中一个就是 root
    return root;
}

要点总结

概念	要点
BST 性质	左子树所有节点 < 根 < 右子树所有节点
中序遍历	结果一定是升序的
查找/插入/删除	都是 $O(h)$，平均 $O(\log n)$，最坏 $O(n)$
后继节点	有右子树→右子树最小；无→往上找第一个"我是左孩子"的祖先
删除两个子节点	用后继（或前驱）替换，然后删除后继

⚠ 常见陷阱

下面是一些你教授特喜欢挖的坑：

BST 性质是"所有节点"，不是"直接子节点"
有序插入会导致退化：1,2,3,4,5 会变成链表
删除有两个子节点时：先替换值，再删除后继/前驱
中序遍历验证 BST：要用严格小于 <，不能有等于
后继/前驱的两种情况：有/无右（左）子树，处理方式完全不同

例Cpt7.1

给定 BST 的前序遍历 [8, 3, 1, 6, 4, 7, 10, 14, 13]，画出这棵树并写出中序遍历结果。

我不知道为啥要有这样一道例题，直接按照规则往下面添叶子就是了。

首先根据前序遍历第一个元素是根。然后找到第一个比根大的元素，它左边是左子树，右边是右子树能够还原树结构：

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

中序遍历：1, 3, 4, 6, 7, 8, 10, 13, 14

如果对遍历方式还是不熟悉的话，回去看看第五章吧。