二叉排序树
一、课上练习
编程练习
- 二叉排序树的添加与查询：L3261
二、知识总结
✨ 核心思想
二叉排序树（Binary Search Tree, BST），也被称为有序二叉树（Ordered Binary Tree）或二叉查找树，是一种特别的二叉树，用于在内存中快速存储、查找、删除和修改数据项。二叉排序树的核心优势在于通过其结构可以提供比普通链表更快的搜索时间。
✨ 定义与性质
二叉排序树是一个二叉树，其中每个节点包含一个键及其关联值，且满足以下性质：
- 节点的左子树只包含键小于该节点键的节点。
- 节点的右子树只包含键大于该节点键的节点。
- 左右子树也必须分别为二叉排序树。
- 没有键值相等的节点（假设所有元素都是唯一的）。
这些性质使得二叉排序树在查找数据时能提供在平均和最坏情况下时间复杂度为 O(log n) 的性能（这里 n 是树中节点的数量）。然而，这种性能依赖于树的高度，如果树极度不平衡，其性能可能退化到 O(n)。
✨ 基本操作
二叉排序树支持多种操作，包括插入、删除、查找和遍历，这些操作通常都可以在 O(log n) 时间内完成（在树平衡的情况下）。
各操作的具体说明：
- 插入：新键的添加根据其值与根节点的比较决定放在左子树还是右子树，并递归地向下进行，直到找到合适的插入位置。
- 删除：删除节点稍微复杂，分为三种情况：
- 删除的节点没有子节点，可以直接删除。
- 删除的节点有一个子节点，可以将其子节点提升到被删除节点的位置。
- 删除的节点有两个子节点，通常使用其右子树的最小节点（或左子树的最大节点）来替换。
- 查找：从根节点开始，根据键值与当前节点键的比较结果向左或向右遍历树。
- 遍历：常见的遍历方法包括中序遍历（这将以升序访问所有节点）、先序遍历和后序遍历。
下面的代码展示了二叉排序树的插入和查询操作：
1#include<iostream>
2using namespace std;
3
4// 定义二叉树的节点结构
5struct Node {
6 int value; // 节点存储的值
7 Node *leftChild; // 左子节点指针
8 Node *rightChild; // 右子节点指针
9};
10
11// 递归插入新节点到二叉搜索树中
12void insert(Node *&node, Node *father, int x) {
13 if (!node) { // 如果当前节点为空，说明找到了插入位置
14 node = new Node; // 创建新节点
15 node->value = x; // 设置新节点的值
16 node->leftChild = NULL; // 初始化左子节点为空
17 node->rightChild = NULL; // 初始化右子节点为空
18 if (father != NULL) { // 如果父节点不为空，根据x值决定是父节点的左子节点还是右子节点
19 if (x <= father->value) {
20 father->leftChild = node;
21 } else {
22 father->rightChild = node;
23 }
24 }
25 return;
26 }
27 // 根据x值递归搜索插入位置
28 if (x <= node->value) {
29 insert(node->leftChild, node, x);
30 } else {
31 insert(node->rightChild, node, x);
32 }
33}
34
35// 查询二叉搜索树中是否存在值为x的节点
36Node *query(Node *node, int x) {
37 if (!node || x == node->value) { // 如果节点为空或找到值为x的节点，返回该节点
38 return node;
39 }
40 if (x < node->value) { // 如果x小于当前节点的值，搜索左子树
41 return query(node->leftChild, x);
42 }
43 // 否则，搜索右子树
44 return query(node->rightChild, x);
45}
46
47int main() {
48 int n = 0; // 操作次数
49 cin >> n;
50 Node *root = NULL; // 根节点初始化为空
51 for (int i = 0; i < n; i++) {
52 string op; // 操作类型
53 int x; // 操作数值
54 cin >> op >> x;
55 if (op == "insert") { // 插入操作
56 if (!root) { // 如果树为空，创建根节点
57 root = new Node;
58 root->value = x;
59 root->leftChild = NULL;
60 root->rightChild = NULL;
61 } else {
62 insert(root, NULL, x); // 插入新节点
63 }
64 } else { // 查询操作
65 Node *node = query(root, x);
66 if (node) {
67 cout << "true" << endl; // 如果找到节点，输出true
68 } else {
69 cout << "false" << endl; // 否则，输出false
70 }
71 }
72 }
73 return 0;
74}✨ 执行示例
下面展示将数据 [5, 3, 8, 1, 4, 7, 9] 依次插入空的二叉排序树的完整过程。
第 1 步：插入 5
- 树为空，5 成为根节点
5第 2 步：插入 3
- 3 < 5，向左走，左子树为空，3 成为 5 的左子节点
5
/
3第 3 步：插入 8
- 8 > 5，向右走，右子树为空，8 成为 5 的右子节点
5
/ \
3 8第 4 步：插入 1
- 1 < 5，向左到 3；1 < 3，向左，左子树为空，1 成为 3 的左子节点
5
/ \
3 8
/
1第 5 步：插入 4
- 4 < 5，向左到 3；4 > 3，向右，右子树为空，4 成为 3 的右子节点
5
/ \
3 8
/ \
1 4第 6 步：插入 7
- 7 > 5，向右到 8；7 < 8，向左，左子树为空，7 成为 8 的左子节点
5
/ \
3 8
/ \ /
1 4 7第 7 步：插入 9
- 9 > 5，向右到 8；9 > 8，向右，右子树为空，9 成为 8 的右子节点
5
/ \
3 8
/ \ / \
1 4 7 9验证 BST 性质： 对这棵树做中序遍历：1 3 4 5 7 8 9，恰好是升序排列！
查找过程示例： 查找值 7
- 7 > 5，向右到 8
- 7 < 8，向左到 7
- 7 == 7，找到！共比较 3 次
退化情况： 如果插入顺序是 [1, 3, 4, 5, 7, 8, 9]（已排序），树会退化为：
11
2 \
3 3
4 \
5 4
6 \
7 5 ...此时查找效率退化为 O(n)。
✨ 平衡问题
虽然二叉排序树在许多情况下都非常有效，但它有一个缺点：如果插入的数据是预排序的，那么生成的二叉树将会非常不平衡，其形状类似于链表（倾斜树），导致大多数操作的效率降低到 O(n)。为了解决这个问题，引入了各种平衡二叉树，如 AVL 树、红黑树等，它们通过在每次插入或删除操作后调整树的结构来保持树的平衡，从而保证了操作的最优时间复杂度。
✨ 应用场景
二叉排序树广泛用于实现符号表、优先队列（通过变种如二叉堆）、数据库索引等数据结构，其中需要高效地支持快速查找和排序操作。理解和能够实现二叉排序树及其操作是计算机科学中数据结构与算法研究的一个基本方面。
✨ 解题步骤详解
以"二叉排序树的添加与查询"为例：
问题： 支持两种操作：insert x 插入值 x，query x 查询值 x 是否存在。
解题步骤：
- 初始化：根节点 root = NULL，表示空树。
- 插入操作：
- 如果树为空（root == NULL），创建新节点作为根。
- 否则从根开始，如果 x 小于当前节点值则进入左子树，否则进入右子树。
- 当到达空位置时，创建新节点并连接到父节点。
- 查询操作：
- 从根开始，比较 x 与当前节点值。
- x 等于当前值：找到，返回 true。
- x 小于当前值：递归搜索左子树。
- x 大于当前值：递归搜索右子树。
- 到达空节点：未找到，返回 false。
✨ 常见错误
- 插入时忘记处理空树的特殊情况：第一次插入时 root 为 NULL，必须单独处理创建根节点。
- 查找时大于/小于的方向搞反：BST 中左子树的值小于根，右子树的值大于根。如果方向搞反会找不到已存在的元素。
- 插入重复值的处理不一致：有些题目要求不允许重复值，有些允许。如果允许重复，需要明确规定相等的值放在左子树还是右子树，并保持一致。
- 删除有两个子节点的节点时替代值选错：应该用右子树的最小值（中序后继）或左子树的最大值（中序前驱）来替代，不能随意选择其他节点。
- 没有考虑退化情况：对于已排序的输入数据，BST 会退化为链表。在竞赛中如果担心这个问题，可以考虑使用 STL 的 set/map（内部使用平衡树）。
三、课后练习
编程练习
- 查找二叉树：L3262