第四章：二叉搜索树 (Binary Search Trees)

学习内容

二叉搜索树（BST）是一种特殊的二叉树，具有"左小右大"的特性，是实现搜索、排序和删除操作的重要数据结构。

二叉搜索树特性

二叉搜索树满足以下性质：

左子树上所有节点的值均小于它的根节点的值

右子树上所有节点的值均大于它的根节点的值

左右子树也分别为二叉搜索树

基本操作

#### 搜索操作

从根节点开始，比较目标值与当前节点值的大小

根据比较结果决定向左子树或右子树继续搜索

时间复杂度：平均 O(log n)，最坏 O(n)

#### 插入操作

从根节点开始，找到合适的插入位置

插入位置一定是某个叶子节点的子节点位置

时间复杂度：平均 O(log n)，最坏 O(n)

#### 删除操作

找到要删除的节点

根据节点的子节点情况分三种情况处理：

1. 节点无子节点：直接删除
2. 节点有一个子节点：用子节点替换该节点
3. 节点有两个子节点：用右子树的最小节点（或左子树的最大节点）替换该节点

重点和难点

重点

1. 理解二叉搜索树的"左小右大"特性
2. 掌握二叉搜索树的基本操作
3. 理解二叉搜索树的性质在算法中的应用

难点

1. 删除操作的三种情况处理
2. 平衡二叉搜索树的概念
3. 二叉搜索树与排序的关系

练习题

基础操作

1. 二叉搜索树中的搜索 (Search in a Binary Search Tree)
- 题目：给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。
- 解题思路：利用BST的性质，递归或迭代地进行搜索。
- 注意点：确保正确利用BST的性质，避免不必要的遍历。

2. 二叉搜索树中的插入操作 (Insert into a Binary Search Tree)
- 题目：给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。
- 解题思路：递归找到合适的插入位置，创建新节点并连接。
- 注意点：处理空树的特殊情况。

进阶题目

1. 删除二叉搜索树中的节点 (Delete Node in a BST)
- 题目：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。
- 解题思路：分三种情况处理删除操作，重点处理有两个子节点的情况。
- 注意点：正确处理各种边界情况，保持BST性质。

2. 验证二叉搜索树 (Validate Binary Search Tree)
- 题目：给定一个二叉树，判断其是否是一个有效的二叉搜索树。
- 解题思路：中序遍历应该得到递增序列；或者通过上下界约束递归验证。
- 注意点：注意不能只比较当前节点与左右子节点，要与整棵子树比较。

解题思路总结

BST的性质应用

1. 搜索优化：利用BST性质可以快速定位元素
2. 排序应用：中序遍历BST得到有序序列
3. 范围查询：可以快速找到指定范围内的所有元素

删除操作的三种情况

1. 无子节点：直接删除节点
2. 一个子节点：用子节点替换当前节点
3. 两个子节点：用后继节点（右子树最小值）或前驱节点（左子树最大值）替换

验证BST的方法

1. 中序遍历法：检查中序遍历结果是否严格递增
2. 上下界法：递归检查每个节点是否在合法范围内

学习时间

建议学习时间：0.5-1天

BST特性及基本操作：30分钟

删除操作详解：45分钟

练习题：1小时