二叉搜索树 (BST) 的性质与退化

单纯的二叉树没有对节点存放的值做任何大小约束，如果想查找某一个值，我们必须遍历整棵树，查找效率依然是 (O(n))。

为了提高查找性能，我们引入了二叉搜索树（Binary Search Tree，简称 BST）。

1. 二叉搜索树的定义

二叉搜索树是一棵特殊的二叉树，它对节点中键值（Key）的分布有如下约束性质：

对任意节点 X：其左子树上所有节点的键值都小于 X 的键值。
对任意节点 X：其右子树上所有节点的键值都大于 X 的键值。
X 的左右子树也分别满足以上性质（递归定义）。

结构图示

这是一棵健康的二叉搜索树：

         [ 10 ]
        /      \
     [ 6 ]    [ 15 ]
     /   \      /
   [ 4 ] [ 8 ] [ 12 ]

思考：如果对这棵树进行中序遍历（左 -> 根 -> 右），结果是什么？答案是：4, 6, 8, 10, 12, 15。它是一个完美升序排列的数组！因此，中序遍历是检验一棵树是否为 BST 的最快办法。

2. 核心操作实现

1) 查找 (Search)

在 BST 中查找目标值 target 的算法非常优雅，类似于在数组中进行二分查找：

如果 target === node.val，直接返回节点。
如果 target < node.val，递归去左子树查找。
如果 target > node.val，递归去右子树查找。

function searchBST(root: TreeNode | null, target: number): TreeNode | null {
  if (root === null || root.val === target) return root;
  return target < root.val
    ? searchBST(root.left, target)
    : searchBST(root.right, target);
}

查找模拟示例

假设我们要在这棵树中查找目标值 8：

         [ 10 ]        <-- 1. 比较 8 < 10，向左子树查找
        /      \
     [ 6 ]    [ 15 ]   <-- 2. 比较 8 > 6，向右子树查找
     /   \      /
   [ 4 ] [ 8 ] [ 12 ]  <-- 3. 比较 8 === 8，查找成功，返回该节点

2) 插入 (Insert)

插入一个新值，我们需要按照“查找”的逻辑向下搜索，直到遇到空位置，将新节点作为叶子节点挂载上去：

function insertBST(root: TreeNode | null, val: number): TreeNode {
  if (root === null) return new TreeNode(val);

  if (val < root.val) {
    root.left = insertBST(root.left, val);
  } else if (val > root.val) {
    root.right = insertBST(root.right, val);
  }
  return root;
}

插入模拟示例

假设我们要在这棵树中插入新值 11：

         [ 10 ]        <-- 1. 比较 11 > 10，向右子树递归
        /      \
     [ 6 ]    [ 15 ]   <-- 2. 比较 11 < 15，向左子树递归
     /   \      /
   [ 4 ] [ 8 ] [ 12 ]  <-- 3. 比较 11 < 12，发现其左子节点为空，挂载新节点
                /
             [ 11 ]    <-- 4. 成功插入新叶子节点 [11]

3. BST 的理想查找复杂度

在最理想的情况下（即树的结构左右均匀分布、接近满二叉树），一棵拥有 (n) 个节点的 BST，其高度为 (\log_2 n)。由于每次比较都会排除掉大约一半的节点，因此查找、插入和删除的平均时间复杂度均为 (O(\log n))。当 (n = 1,000,000) 时，我们仅需比较大约 20 次！

4. 致命缺陷：链表化退化

BST 看上去非常完美，但它在一种特定的使用场景下会暴露出致命缺陷。

如果我们顺序插入一组已经排好序的数据，例如：1, 2, 3, 4, 5：

插入 1 作为根节点。
插入 2（比 1 大），挂在右边。
插入 3（比 2 大），挂在右边。
插入 4、5……

最终形成的树会是这个样子：

后果

此时，二叉搜索树退化成了一个普通的单链表！

树的高度从 (\log_2 n) 退化为了 (n)。
查找时间复杂度从期望的 (O(\log n)) 重新恶化回了 (O(n))。

为了阻止这种“退化”现象的发生，数据结构学家们提出了一个要求：树在插入和删除新元素时，必须能够“自我调节”，保持左右子树的高度平衡。这就引出了下一节的内容：平衡二叉树。

1. 二叉搜索树的定义​

结构图示​

2. 核心操作实现​

1) 查找 (Search)​

查找模拟示例​

2) 插入 (Insert)​

插入模拟示例​

3. BST 的理想查找复杂度​

4. 致命缺陷：链表化退化​

后果​