二叉搜索树

1. 理论推导过程

二叉搜索树的基本定义

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其每个节点都满足以下性质：

• 左子树所有节点的键值均小于根节点的键值；

• 右子树所有节点的键值均大于根节点的键值；

• 左右子树本身也是二叉搜索树。

这一性质保证了在树中查找一个元素时，可以利用二分查找的思想，从根节点出发，根据键值大小选择左子树或右子树，从而大大减少查找次数。

理论推导

1. 查找操作：
   对于给定的键值 x：

   • 从根节点开始比较，如果 x 等于当前节点的键值，则查找成功；

   • 如果 x 小于当前节点的键值，则递归地在左子树中查找；

   • 如果 x 大于当前节点的键值，则递归地在右子树中查找。

2. 插入操作：
   插入一个新键时，利用查找操作定位到应插入的位置（即找到一个空子树），然后将新键作为该空位置的节点插入，同时保证新树依然满足 BST 的定义。

3. 删除操作：
   删除一个节点时需要考虑三种情况：

   • 叶子节点：直接删除即可；

   • 只有一个子树的节点：用子树替代该节点；

   • 有两个子树的节点：通常找该节点右子树中最小的节点（或左子树中最大的节点）来替代，然后删除该节点，保证树的有序性。

---

2. 使用步骤

以常见操作为例，说明 BST 的使用步骤：

查找操作

1. 从根节点开始；

2. 若当前节点为空，则返回“未找到”；

3. 比较 x 与当前节点的键值：

   • 若相等，则查找成功；

   • 若 x 小于当前节点键值，则移动到左子树；

   • 若 x 大于当前节点键值，则移动到右子树；

4. 重复步骤 2-3，直到查找结束。

插入操作

1. 从根节点开始；

2. 若当前节点为空，则插入新节点；

3. 比较新键 x 与当前节点键值：

   • 若 x 小于当前节点键值，则递归插入到左子树；

   • 若 x 大于当前节点键值，则递归插入到右子树；

4. 插入后返回根节点，保证树结构不变。

删除操作

1. 查找要删除的节点；

2. 根据该节点的子树情况分类讨论：

   • 叶子节点：直接删除；

   • 一个子树：用子树代替该节点；

   • 两个子树：找右子树中最小节点（或左子树中最大节点）替换当前节点，然后删除替换节点；

3. 调整链接，保证 BST 性质不变。

---

3. 时间复杂度推导

• 平均情况：
  在一棵平衡的 BST 中，每次操作沿着树的高度进行查找、插入或删除。
  平均情况下，树的高度为 O(log⁡n) （n  为节点数），因此平均时间复杂度为：

  • 查找：O(log⁡n) 

  • 插入：O(log⁡n) 

  • 删除：O(log⁡n) 

• 最坏情况：
  当 BST 退化为链表（例如插入的键已经有序），树的高度为 O(n) ；
  此时，操作的时间复杂度退化为：

  • 查找：O(n) 

  • 插入：O(n) 

  • 删除：O(n) 

---

4. 应用场景

二叉搜索树因其高效的查找、插入和删除操作，在以下场景中被广泛应用：

• 字典/映射数据结构： 用于存储键值对，实现快速查找和动态更新。

• 集合操作： 用于集合的存储和去重，支持高效的范围查询。

• 数据库索引： 在数据库中，通过 BST 或其平衡变种（如 AVL 树、红黑树）加速数据检索。

• 符号表： 在编译器和解释器中维护标识符与其属性的映射。

---

5. 示例

假设我们有一组待插入的键：[50, 30, 70, 20, 40, 60, 80]，我们一步步构造 BST。

插入过程

1. 插入 50

   • 当前树为空，50 成为根节点。
     当前树结构：

   50

2. 插入 30

   • 比较 30 与根 50，30 < 50，插入到左子树。
     当前树结构：

       50/30
   

3. 插入 70

   • 比较 70 与根 50，70 > 50，插入到右子树。
     当前树结构：

       50/  \30    70
   

4. 插入 20

   • 20 < 50，进入左子树；20 < 30，插入到 30 的左侧。
     当前树结构：

         50/  \30    70/
   20
   

5. 插入 40

   • 40 < 50，进入左子树；40 > 30，插入到 30 的右侧。
     当前树结构：

         50/  \30    70/  \
   20    40
   

6. 插入 60

   • 60 > 50，进入右子树；60 < 70，插入到 70 的左侧。
     当前树结构：

         50/  \30    70/  \   /
   20    40 60
   

7. 插入 80

   • 80 > 50，进入右子树；80 > 70，插入到 70 的右侧。
     最终 BST 结构：

         50/  \30    70/  \   / \
   20    40 60  80
   

查找操作示例

例如查找 60：

• 从根 50 开始：60 > 50，进入右子树；

• 在节点 70：60 < 70，进入左子树；

• 在节点 60：找到目标。

删除操作示例

例如删除 70：

• 节点 70 有两个子树，常见做法是找右子树中最小的节点，此处为 80 的左子树为空，则 80 为最小；

• 或者找左子树中最大的节点（这里为 60）。
  假设我们选择使用 60 替换 70：

• 将 60 替换到 70 的位置，然后删除原来的 60 节点（由于 60 为叶子节点，直接删除）。
  最终树结构变为：

        50/  \30    60/  \     \
  20    40    80