算法 - 13. 二叉搜索树 (BST)
algorithmsdata-structurestreesearching
By sko•10/9/2025•21 min read
何时使用二叉搜索树
当你需要通过高效操作维护动态变化的有序集合时，使用二叉搜索树。虽然最常用于搜索有序数据，但BST可以适用于：
- 数据库索引（经典用例）- B树和B+树是BST的变体
- 频繁更新的优先队列（当堆操作不够用时）
- 查找值范围内的所有元素 - 例如：80-90之间的所有分数。BST返回范围内的实际元素（如"显示所有价格在$50-$100之间的产品"），而线段树擅长范围聚合查询（如"索引3到7的元素之和"）
- 顺序统计 - 查找第k小/大的元素
- 区间树 - 基于BST的结构，用于管理重叠区间（如下午2-4点、3-5点的日历事件）。高效回答"哪些事件与下午3:30重叠？"或"找出所有与下午2-3点时段冲突的会议"
- 文件系统 - 目录结构和文件组织
- 任何需要通过频繁插入/删除维护有序的问题
示例问题
音乐播放列表管理器：你正在构建一个音乐播放器，它按歌曲标题排序维护播放列表。给定添加歌曲的操作，如["Bohemian Rhapsody", "Imagine", "Hey Jude", "Let It Be", "Yesterday", "Come Together"]，高效地：
- 在保持字母顺序的同时添加新歌曲
- 搜索特定歌曲以播放它们
- 从播放列表中删除歌曲
- 查找以特定字母或前缀开头的所有歌曲
处理所有操作后：
- BST按字母顺序维护歌曲
- 搜索"Hey Jude"平均需要O(log n)时间
- 我们可以通过中序遍历以有序方式获取所有歌曲（访问左子树→当前节点→右子树，得到字母顺序）
- 像"所有以H开头的歌曲"这样的范围查询很高效（这是按字母顺序查找"H"和"I"之间的所有值）
答案：BST自动维护有序，使所有这些操作高效，无需手动排序。
二叉搜索树实际做什么
二叉搜索树是一种分层数据结构，通过一个简单的规则以有序方式维护元素。它提供三个核心操作：
- SEARCH：查找元素是否存在于树中
- INSERT：在维护BST属性的同时添加新元素
- DELETE：删除元素并重新组织树
（注意：UPDATE不是单独的操作，因为更改值需要DELETE + INSERT - 新值可能属于树中的不同位置）
把它想象成按字母顺序组织音乐播放列表：
- SEARCH："这首歌在我的播放列表中吗？"
- INSERT："在正确的字母位置添加这首新歌"
- DELETE："删除这首歌并保持播放列表有序"
操作如何工作
SEARCH操作 - "这个值在树中吗？"
当你调用search(root, 42)时，它：
- 从根节点开始
- 将42与当前节点的值比较
- 如果42较小则向左，较大则向右
- 如果找到则返回true，如果到达null则返回false
- 关键效率：在每一步消除剩余树的一半
INSERT操作 - "在维护顺序的同时添加这个值"
当你调用insert(root, 35)时，它：
- 遵循与搜索相同的比较路径（较小向左，较大向右）
- 保证会遇到一个空位置（null）- 原因：要么我们发现值已存在（跳过插入），要么我们继续向下直到到达叶节点的空子节点
- 在该空位置创建一个值为35的新节点
- BST属性维护：左子树中的所有值 < 节点 < 右子树中的所有值
示例 - 插入35：
当前树: 插入35的路径: 插入后:
50 1. 在50: 35<50, 向左 50
/ \ 2. 在30: 35>30, 向右 / \
30 70 3. 在40: 35<40, 向左 30 70
/ \ 4. 遇到NULL（空）! / \
20 40 5. 在这里创建节点 20 40
/
35DELETE操作 - "删除这个值并重新组织"
当你调用delete(root, 50)时，它处理三种情况：
-
叶节点：简单地删除它（不影响其他节点）
-
一个子节点：用其子节点替换节点（子节点及其所有后代保持相对顺序）
-
两个子节点：找到中序后继（右子树中的最小值），替换值，删除后继
为什么"中序后继" = "右子树中的最小值"：这个术语来自有序顺序。如果你按有序顺序列出所有值，"后继"是你要删除的值之后的下一个值。对于有两个子节点的节点，这个下一个值总是其右子树中的最小值。例如：在[30, 40, 50, 60, 70]中，要删除50，我们需要60（下一个值），这是通过向右走一次（到70的子树），然后尽可能向左走（找到60）来找到的。
为什么"尽可能向左走"找到最小值：在BST中，较小的值总是在左边。所以从任何节点开始，如果你一直向左走直到不能再走，你将到达该子树中的最小值。这正是中序遍历找到下一个元素的方法 - 在访问一个节点后，它进入右子树，然后立即尽可能向左走。
因此，中序后继是右子树中最左边的节点。
为什么这些维护BST顺序：
一个子节点的情况 - 删除30（只有右子节点40）：
删除前: 删除后: 为什么有效:
50 50 40的子树中的所有节点（40, 35, 45）
/ \ / \ 都 > 30 且 < 50
30 70 40 70 它们仍然 > 30的位置 且 < 50
\ / \ 顺序被保留！
40 35 45
/ \
35 45两个子节点的情况 - 删除50：
删除前: 删除后: 为什么有效:
50 60 60是右子树中最小的
/ \ / \ 所以: 60 > 左边的所有（30,40）
30 70 30 70 并且: 60 < 右边剩余的所有（70,80）
/ \ \ 完美替换！
60 80 80这些操作何时发生
这些操作只在你明确调用它们时发生：
const bst = new BinarySearchTree();
// INSERT: 明确添加元素
bst.insert(50); // 创建根
bst.insert(30); // 在50的左边
bst.insert(70); // 在50的右边
bst.insert(40); // 在30的右边
// SEARCH: 检查元素是否存在
let found = bst.search(40); // 返回true
let notFound = bst.search(25); // 返回false
// DELETE: 删除元素
bst.delete(30); // 删除30，重新组织树BST的美妙之处在于它自动维护有序 - 你永远不需要手动排序或重新组织数据！
最重要的洞察
每个节点的BST属性（左 < 父 < 右）创建了一个用于搜索的决策树 - 通过始终遵循"较小向左，较大向右"，我们在每一步消除一半的搜索空间，在平衡树中实现O(log n)搜索。
心理笔记：算法的天才之处在于将有序编码到树结构本身中。在每个节点，我们只需要根据比较做出一个决定：向左或向右。每个级别的这个简单的二元决定自动维护有序数据并使二分搜索无需数组即可实现。
决策框架
BST操作涉及这些关键决策：
搜索期间：
- 当前节点是null吗？返回未找到
- 目标等于当前值吗？返回找到
- 目标小于当前值吗？向左走
- 目标大于当前值吗？向右走
插入期间：
- 将新值与当前节点比较（就像搜索一样）
- 如果新值较小，向左走；如果较大，向右走
- 继续向下直到找到一个空位置（null）
- 在该空位置创建新节点
删除期间（最复杂）：
- 没有子节点（叶子）？简单地删除
- 一个子节点？用该子节点替换
- 两个子节点？找到中序后继，交换值，删除后继
为什么BST属性很重要
BST属性确保所有操作都可以忽略整个子树：
没有BST属性（未排序的树）：
要找到值35:
50
/ \
70 30
/ \ / \
20 40 60 10
必须检查所有7个节点 - O(n)时间！有BST属性：
要找到值35:
50
/ \
30 70 ← 忽略整个右子树！
/ \
20 40 ← 只检查30的左边，忽略20！
路径: 50 → 30 → 40 → 未找到（只有3次检查）BST属性保证：
- 左子树中的所有值 < 节点值
- 右子树中的所有值 > 节点值
- 这递归地应用于每个子树
- 结果：我们可以在每一步消除约50%的剩余节点
这就是为什么平衡BST实现O(log n)操作 - 高度决定所需的最大比较次数！
代码
// 树的节点结构
class TreeNode {
constructor(value) {
this.value = value;
this.left = null; // 左子节点（较小的值）
this.right = null; // 右子节点（较大的值）
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
// SEARCH: 查找值是否存在于树中
search(targetValue) {
return this.searchFromNode(this.root, targetValue);
}
searchFromNode(currentNode, targetValue) {
// 基本情况：到达路径末尾
const reachedEndOfPath = currentNode === null;
if (reachedEndOfPath) {
return false; // 未找到值
}
// 提取当前节点的值进行比较
const currentValue = currentNode.value;
// 决策框架：三向比较
const foundTarget = targetValue === currentValue;
const shouldSearchLeft = targetValue < currentValue;
const shouldSearchRight = targetValue > currentValue;
if (foundTarget) {
return true; // 成功找到目标！
}
if (shouldSearchLeft) {
// 目标较小 - 只搜索左子树
const leftSubtree = currentNode.left;
return this.searchFromNode(leftSubtree, targetValue);
}
if (shouldSearchRight) {
// 目标较大 - 只搜索右子树
const rightSubtree = currentNode.right;
return this.searchFromNode(rightSubtree, targetValue);
}
}
// INSERT: 在维护BST属性的同时添加新值
insert(newValue) {
// 从根开始插入，必要时更新根
this.root = this.insertIntoSubtree(this.root, newValue);
}
insertIntoSubtree(currentNode, newValue) {
// 基本情况：为新节点找到空位置
const foundEmptySpot = currentNode === null;
if (foundEmptySpot) {
const newNode = new TreeNode(newValue);
return newNode;
}
// 提取当前值进行比较
const currentValue = currentNode.value;
// 基本情况：发现重复 - 不需要插入
const isDuplicate = newValue === currentValue;
if (isDuplicate) {
return currentNode; // 返回未更改的节点
}
// 决策框架：确定插入方向
const insertToLeft = newValue < currentValue;
if (insertToLeft) {
// 新值较小 - 插入左子树
const updatedLeftSubtree = this.insertIntoSubtree(
currentNode.left,
newValue
);
currentNode.left = updatedLeftSubtree;
} else {
// 新值较大 - 插入右子树
const updatedRightSubtree = this.insertIntoSubtree(
currentNode.right,
newValue
);
currentNode.right = updatedRightSubtree;
}
return currentNode;
}
// DELETE: 删除值并维护BST属性
delete(valueToDelete) {
// 从根开始删除，必要时更新根
this.root = this.deleteFromSubtree(this.root, valueToDelete);
}
deleteFromSubtree(currentNode, valueToDelete) {
// 基本情况：在树中未找到值
const nodeNotFound = currentNode === null;
if (nodeNotFound) {
return null;
}
// 提取当前值进行比较
const currentValue = currentNode.value;
// 决策框架：定位要删除的节点
const searchLeft = valueToDelete < currentValue;
const searchRight = valueToDelete > currentValue;
const foundNodeToDelete = valueToDelete === currentValue;
if (searchLeft) {
// 要删除的值在左子树中
const updatedLeftSubtree = this.deleteFromSubtree(
currentNode.left,
valueToDelete
);
currentNode.left = updatedLeftSubtree;
return currentNode;
}
if (searchRight) {
// 要删除的值在右子树中
const updatedRightSubtree = this.deleteFromSubtree(
currentNode.right,
valueToDelete
);
currentNode.right = updatedRightSubtree;
return currentNode;
}
if (foundNodeToDelete) {
// 找到要删除的节点 - 处理三种情况
// 决策框架：基于子节点数量的删除情况
const hasNoChildren =
currentNode.left === null && currentNode.right === null;
const hasOnlyRightChild =
currentNode.left === null && currentNode.right !== null;
const hasOnlyLeftChild =
currentNode.right === null && currentNode.left !== null;
const hasBothChildren =
currentNode.left !== null && currentNode.right !== null;
if (hasNoChildren) {
// 情况1：叶节点 - 简单地删除
return null;
}
if (hasOnlyRightChild) {
// 情况2a：只有右子节点存在 - 用它替换
const rightChild = currentNode.right;
return rightChild;
}
if (hasOnlyLeftChild) {
// 情况2b：只有左子节点存在 - 用它替换
const leftChild = currentNode.left;
return leftChild;
}
if (hasBothChildren) {
// 情况3：两个子节点都存在 - 使用后继策略
// 找到中序后继（右子树中的最小值）
const rightSubtree = currentNode.right;
const successorNode = this.findMinimumNode(rightSubtree);
const successorValue = successorNode.value;
// 用后继的值替换当前节点的值
currentNode.value = successorValue;
// 从右子树中删除后继（它最多有一个子节点）
const updatedRightSubtree = this.deleteFromSubtree(
rightSubtree,
successorValue
);
currentNode.right = updatedRightSubtree;
return currentNode;
}
}
}
// 辅助函数：在子树中找到具有最小值的节点
findMinimumNode(startNode) {
// 最小值总是最左边的节点
let currentNode = startNode;
// 继续向左走直到不能再走
while (currentNode.left !== null) {
currentNode = currentNode.left;
}
// 这是最左边（最小）的节点
return currentNode;
}
// 额外功能：中序遍历（返回有序数组）
getSortedValues() {
const sortedArray = [];
this.collectInOrder(this.root, sortedArray);
return sortedArray;
}
collectInOrder(currentNode, resultArray) {
// 基本情况：null节点不贡献任何内容
const isNullNode = currentNode === null;
if (isNullNode) {
return;
}
// 中序遍历：左 -> 当前 -> 右
const leftSubtree = currentNode.left;
const currentValue = currentNode.value;
const rightSubtree = currentNode.right;
// 步骤1：处理左子树中的所有值（较小的值）
this.collectInOrder(leftSubtree, resultArray);
// 步骤2：处理当前节点的值
resultArray.push(currentValue);
// 步骤3：处理右子树中的所有值（较大的值）
this.collectInOrder(rightSubtree, resultArray);
}
}
// === 使用示例：音乐播放列表管理器 ===
function demonstrateMusicPlaylist() {
const playlist = new BinarySearchTree();
// 要添加到播放列表的歌曲
const songsToAdd = [
"Bohemian Rhapsody",
"Imagine",
"Hey Jude",
"Let It Be",
"Yesterday",
"Come Together",
];
// 将每首歌添加到播放列表
console.log("=== 向播放列表添加歌曲 ===");
for (const songTitle of songsToAdd) {
playlist.insert(songTitle);
console.log(`✓ 已添加: "${songTitle}"`);
}
// 测试搜索功能
console.log("\n=== 测试歌曲搜索 ===");
const songToFind = "Hey Jude";
const songExists = playlist.search(songToFind);
console.log(`"${songToFind}"是否存在？ ${songExists}`); // true
const missingSong = "Stairway to Heaven";
const notInPlaylist = playlist.search(missingSong);
console.log(`"${missingSong}"是否存在？ ${notInPlaylist}`); // false
// 以有序方式显示所有歌曲
console.log("\n=== 所有歌曲（按字母顺序） ===");
const allSongsInOrder = playlist.getSortedValues();
console.log(allSongsInOrder);
// 输出: ["Bohemian Rhapsody", "Come Together", "Hey Jude", "Imagine", "Let It Be", "Yesterday"]
// 从播放列表中删除一首歌
console.log("\n=== 删除歌曲 ===");
const songToRemove = "Hey Jude";
console.log(`正在从播放列表中删除"${songToRemove}"...`);
playlist.delete(songToRemove);
// 显示更新后的播放列表
const updatedPlaylist = playlist.getSortedValues();
console.log("更新后的播放列表:", updatedPlaylist);
// 输出: ["Bohemian Rhapsody", "Come Together", "Imagine", "Let It Be", "Yesterday"]
// 可视化最终树结构
console.log("\n=== 最终树结构 ===");
console.log(`
"Imagine"
/ \\
"Come Together" "Let It Be"
/ \\
"Bohemian Rhapsody" "Yesterday"
`);
}
// 运行演示
demonstrateMusicPlaylist();疑惑消除器
常见疑惑："删除有两个子节点的节点时，为什么我们特别选择中序后继（右子树中的最小值）？为什么不是中序前驱（左子树中的最大值）或任何其他节点？"
这似乎是随意的 - 算法似乎也可以使用前驱，那么为什么每本教科书都坚持使用后继？让我们探索为什么这个选择很重要。
为什么这似乎是随意的
考虑删除有两个子节点的节点50：
50 (删除这个)
/ \
30 70
/ \ / \
20 40 60 80
选项:
1. 用前驱(40)替换 - 左子树中的最大值
2. 用后继(60)替换 - 右子树中的最小值
3. 用...70替换？30？为什么不行？前驱和后继似乎都有效 - 它们都维护BST属性！
关键洞察：维护BST属性
这里是关键要求：替换值必须：
- 大于左子树中的所有值
- 小于右子树中的所有值
- 容易从其当前位置删除
让我们检查每个选项：
选项1：中序前驱（40）
删除前: 用40替换50后:
50 40
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 - 60 80
✓ 40 > 左子树中的所有值（20, 30）
✓ 40 < 右子树中的所有值（60, 70, 80）
✓ 从左子树中删除40很容易（它是叶子或只有一个子节点）选项2：中序后继（60）
删除前: 用60替换50后:
50 60
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 40 - 80
✓ 60 > 左子树中的所有值（20, 30, 40）
✓ 60 < 右子树中的所有值（70, 80）
✓ 从右子树中删除60很容易（它是叶子或只有一个子节点）选项3：像70这样的随机节点
用70替换50后:
70
/ \
30 70 (重复?!)
/ \ / \
20 40 60 80
✗ 70不小于右子树中的所有值（它等于70，大于60）
✗ 创建重复或违反BST属性为什么特别是后继（或前驱）？
数学保证：中序后继和前驱是满足所有要求的唯一两个值：
-
中序后继 = 大于被删除节点的最小值
- 保证 > 左子树中的所有值
- 保证 < 右子树中的所有值（除了自己）
- 总是最多有一个子节点（按定义没有左子节点）
-
中序前驱 = 小于被删除节点的最大值
- 保证 < 右子树中的所有值
- 保证 > 左子树中的所有值（除了自己）
- 总是最多有一个子节点（按定义没有右子节点）
-
任何其他值 = 至少违反一个子树的BST属性
为什么后继略受青睐
虽然两者都正确工作，但后继经常被选择以保持一致性：
- 标准约定：大多数教科书为了统一使用后继
- 平衡考虑：在随机删除中，交替可能平衡更好
- 实现简单性：找到最小值（最左边）通常比找到最大值更清晰
- 历史先例：早期BST论文使用后继
美丽的属性：为什么后继/前驱最多只有一个子节点
这是使删除高效的优雅部分：
中序后继（右子树中的最小值）：
节点
\
右子树
/
后继 (没有左子节点!)
\
可能有右子节点- 如果后继有左子节点，那个子节点会更小
- 但那样它就是后继，而不是这个节点
- 矛盾！所以后继只能有右子节点
中序前驱（左子树中的最大值）：
节点
/
左子树
\
前驱 (没有右子节点!)
/
可能有左子节点- 如果前驱有右子节点，那个子节点会更大
- 但那样它就是前驱，而不是这个节点
- 矛盾！所以前驱只能有左子节点
这个属性保证当我们从其位置删除后继/前驱时，我们只面对情况1（叶子）或情况2（一个子节点）- 永远不会再次面对复杂的情况3！
具体示例：为什么算法是最优的
让我们跟踪一次删除，看看为什么这种方法是优雅的：
// 从这棵树中删除50:
// 50
// / \
// 30 70
// / \ / \
// 20 40 60 80
// \
// 65
//
deleteNode(root, 50):
// 找到节点50 - 有两个子节点
// 找到后继：向右一次，然后向左直到null
successor = findMin(70的子树) = 60
// 用60替换50的值
node.value = 60
// 现在从右子树中删除60
// 60有一个子节点(65)，所以这是情况2 - 简单！
// 最终的树:
// 60
// / \
// 30 70
// / \ / \
// 20 40 65 80算法优雅地将复杂的两子节点情况减少为更简单的一子节点情况！
结论：使用中序后继（或前驱）不是随意的 - 它们是替换被删除节点时维护BST属性的唯一值。它们之间的选择是次要的实现细节，但使用其中之一的数学要求是绝对的。