二叉搜索树

3.1 二叉搜索树 (BST) 的定义

二叉搜索树 (BST) —— 是一种具有以下特性的二叉树：

• 对于任意节点，左子树只包含比该节点的键小的节点。
• 对于任意节点，右子树只包含比该节点的键大的节点。
• 每个节点的两个子树也都是二叉搜索树。

BST 的例子：

BST 是 Binary Search Tree 的缩写，字面意思是“二叉搜索树”。实际上，这是一种以“树”的形式组织数据的方法，可以非常快速地进行搜索。树的结构实际上是一种隐藏/巧妙的元素排序方式。

中序遍历 (in-order traversal)

遍历任务 —— 以特定方式形成节点列表（或节点中的数据，这取决于术语，并在实践中具有意义）。中序遍历——这种遍历方式中，树的根节点位于左子树和右子树对应遍历结果之间。

结合二叉搜索树的特性（关于不等式的，看理论），这意味着中序遍历二叉搜索树将为我们形成一个排序的节点列表——很酷吧！这就是之前定义的树的遍历方式：

3.2 BST 的工作原理和属性

工作原理：

• 数据组织：BST 组织数据以确保高效的搜索、插入和删除元素。
• 递归结构：BST 中的每个节点都遵循与树根相同的规则，使其结构递归。
• 平衡性：为了确保最佳性能，BST 应该是平衡的，即左右子树的高度应该大致相同。

BST 的属性：

• 有序性： 在任何时刻都可以按 "in-order" 顺序遍历树 （左子树 → 当前节点 → 右子树），以获得所有元素的排序顺序。
• 操作时间：
  • 平均情况下，搜索、插入和删除操作的时间复杂度为 O(log n)，其中 n 是节点数量。
  • 在最坏的情况下（如果树不平衡），操作时间可能达到 O(n)。
• 唯一键：BST 中的所有键必须是唯一的，以保持有序性。

3.3 主要操作

1. 插入 (Insertion)：

工作原理：

• 从根节点开始。
• 将新节点的键与当前节点的键进行比较。
• 如果新键较小，则移动到左子树，如果较大，则移动到右子树。
• 重复此过程，直到找到合适的位置插入新节点（左或右子节点不存在）。

算法：

1. 如果树为空，新节点成为根节点。
2. 否则递归地找到正确的位置并添加新节点。

2. 删除 (Deletion)：

工作原理：

• 找到要删除的节点。
• 考虑三种情况：
• 节点是叶节点（没有子节点）：直接删除节点。
• 节点有一个子节点：用其子节点替换该节点。
• 节点有两个子节点：找到右子树中的最小节点（或左子树中的最大节点），将其值复制到要删除的节点中，然后递归地删除右子树中的最小节点。

算法：

1. 找到具有指定键的节点。
2. 根据情况执行相应的删除和节点重新分配。

3. 搜索 (Search)：

工作原理：

• 从根节点开始。
• 将目标节点的键与当前节点的键进行比较。
• 如果键相同，返回节点。
• 如果键较小，则移动到左子树，如果较大，则移动到右子树。
• 重复此过程，直到找到具有目标键的节点或达到树的末端（在这种情况下，节点未找到）。

算法：

1. 如果树为空或节点键与目标键匹配，返回节点。
2. 如果目标节点的键较小，递归搜索左子树。
3. 如果目标节点的键较大，递归搜索右子树。

3.4 使用 BST 解决的示例任务

1. 在动态集合中搜索元素

需要维护一个数字集合，可以向其中添加新元素，删除现有元素，并快速检查集合中是否有指定的数字。

使用 BST 的解决方案：

• 将新元素插入到树中。
• 删除现有元素。
• 在树中搜索元素。

使用示例：

支持系统中注册用户的列表，用户可以添加和删除，系统需要快速检查用户是否已注册。

2. 查找最小和最大元素

需要快速找到数据集中的最小值和最大值。

使用 BST 的解决方案：

• 最小元素位于树的最左侧节点。
• 最大元素位于树的最右侧节点。

使用示例：

支持跟踪股票价格的系统，需要快速找到当前时刻的最低和最高价格。

3. 检查表达式的平衡

给定一个数学表达式，需要检查其是否在开闭括号数量上是平衡的。

使用 BST 的解决方案：

使用 BST 存储检查括号平衡的中间状态。

使用示例：

解析和编译代码时，需要检查表达式中的括号是否正确配对。

4. 构建字典

需要创建一个数据结构来存储字典，字典中的单词可以被添加、删除和快速找到。

使用 BST 的解决方案：

• 按照字母顺序将单词插入到树中。
• 根据键搜索单词。

使用示例：

文本自动修正系统，需要快速找到和纠正单词。