二叉搜索树（BST）

---

1. 定义

二叉搜索树（BST） 是一棵 二叉树，它满足以下性质：

1. 左子树节点值 < 根节点值
2. 右子树节点值 > 根节点值
3. 左右子树也是二叉搜索树

也就是说，每个节点的值大于左子树所有节点，小于右子树所有节点。

BST 示例组：

      4                   5                 1
     / \                 /                   \
    2   6               3                     2
   / \ / \             / \                     \
  1  3 5  7           2   4                     3
                                                 \
                                                  4

2. 特点

• 有序性：中序遍历 BST → 节点值按升序排列
• 动态查找：插入、删除、查找操作基于树结构
• 时间复杂度：
  • 最坏情况：O(n)（退化为链表）
  • 平均情况：O(log n)（树大致平衡时）

3. 基本操作

1. 查找

   • 从根节点开始，若目标 < 当前节点 → 左子树
   • 目标 > 当前节点 → 右子树
   • 目标 = 当前节点 → 找到

2. 插入

   • 类似查找路径，找到合适叶子位置插入
   • 不破坏 BST 性质

3. 删除

   • 删除叶子节点 → 直接删除
   • 删除有一个子节点 → 用子节点替代
   • 删除有两个子节点 → 用右子树最小节点或左子树最大节点替代，然后递归删除

4. 缺点

• 高度不平衡时性能下降
  • 若插入顺序为有序序列，BST 退化为链表 → 查找/插入/删除 O(n)
• 因此在实际应用中，经常结合 平衡策略 → AVL 树、红黑树等