二叉搜索树（BST）

二叉搜索树（Binary Search Tree）是一种动态查找结构：对于每个节点，其左子树所有关键字均小于该节点，右子树所有关键字均大于该节点。 中序遍历 BST 可得到有序序列，这一性质使得查找、插入和删除操作均可在 O(h) 时间内完成（h 为树高）。

BST 查找

查找目标关键字 key：从根节点出发，若 key < 当前节点，走左子树；若 key > 当前节点，走右子树；相等则命中。

查找过程模拟

以 BST {8, 5, 12, 3, 7, 10, 14}、目标 key = 10 为例：

步骤图：从根 8 开始，10 > 8，走右子树

1/3

BST 插入

插入新关键字时，先按查找逻辑找到其应插入的位置（空节点处），再创建新节点挂接。插入后仍满足 BST 性质。

插入过程模拟

向 BST 中插入 key = 6：

步骤图：从根出发查找插入位置，8→5→7，到达 7 的左子位置

1/3

BST 删除

删除分三种情况：

1. 叶节点：直接删除。
2. 只有一个子节点：用子节点替代被删节点。
3. 有两个子节点：用中序后继（右子树最左节点）替换，再删除该后继。

删除过程模拟

删除节点 5（有两个子节点 3、7）：

步骤图：目标节点 5 有两个子节点，需找中序后继

1/3

算法特性

• 时间复杂度：平均 O(log n)；最坏情况（退化为链表）O(n)。
• 空间复杂度：O(n)，每个元素对应一个节点。
• 中序遍历：始终得到有序序列，可用于验证 BST 结构正确性。
• 退化问题：按有序序列插入导致树退化为链表；AVL 树和红黑树通过旋转避免此问题。

Baseline 任务：BST 实现

任务内容

完成 bst_avl.cpp，实现以下 BST 功能：

1. BST 插入 void insert(int key)
   • 保持左子树关键字小于根、右子树关键字大于根
2. BST 查找 bool search(int key)
   • 返回目标关键字是否存在
3. BST 删除 void remove(int key)
   • 处理三种删除情况，保持 BST 性质
4. 中序遍历 void inorder()
   • 输出有序序列用于验证

文件结构

• bst_avl.h：BST 与 AVL 树接口声明
• bst_avl.cpp：核心实现
• test.cpp：测试程序

验证方式

• 编译：g++ -std=c++17 test.cpp bst_avl.cpp -o testBSTAVL
• 运行：./testBSTAVL