数据结构与算法 / 系统课时
二叉搜索树插入
二叉搜索树插入
二叉搜索树插入的关键不是把节点放进任意空位,而是沿比较结果向左或向右下降,直到找到唯一合法的空链接。本课将实现迭代插入,并用树高解释为什么相同数量的节点可能产生完全不同的插入成本。
学习目标
- 掌握二叉搜索树的插入路径与重复键处理规则。
- 实现完整的节点插入、中序遍历和查找程序。
- 根据树高分析平均与最坏情况下的时间复杂度。
插入规则与执行路径
对当前节点 current 比较待插入键 key:
key < current.key时进入左子树。key > current.key时进入右子树。- 两者相等时按既定策略处理;本例选择忽略重复键。
- 目标方向的子链接为空时,在该位置创建新节点。

一次插入只访问根到目标位置的一条路径,因此时间复杂度是 ,其中 为树高。树较平衡时, 接近 ;若键按单调顺序插入,树可能退化为链表,此时 。迭代实现只保存当前节点引用,额外空间为 。
完整可运行示例
将代码保存为 BstInsertDemo.java。程序依次插入多个整数,随后通过中序遍历验证有序性,并输出树高和查找结果。
java
import java.util.ArrayList;
import java.util.List;
public class BstInsertDemo {
private static final class Node {
int key;
Node left;
Node right;
Node(int key) {
this.key = key;
}
}
public static void main(String[] args) {
int[] keys = {8, 3, 10, 1, 6, 14, 4, 7, 13};
Node root = null;
for (int key : keys) {
root = insert(root, key);
}
System.out.println("中序遍历: " + inOrder(root));
System.out.println("树高: " + height(root));
System.out.println("查找 7: " + contains(root, 7));
}
private static Node insert(Node root, int key) {
if (root == null) {
return new Node(key);
}
Node current = root;
while (true) {
if (key < current.key) {
if (current.left == null) {
current.left = new Node(key);
break;
}
current = current.left;
} else if (key > current.key) {
if (current.right == null) {
current.right = new Node(key);
break;
}
current = current.right;
} else {
break;
}
}
return root;
}
private static boolean contains(Node root, int key) {
Node current = root;
while (current != null) {
if (key == current.key) {
return true;
}
current = key < current.key ? current.left : current.right;
}
return false;
}
private static int height(Node root) {
if (root == null) {
return 0;
}
return 1 + Math.max(height(root.left), height(root.right));
}
private static List<Integer> inOrder(Node root) {
List<Integer> result = new ArrayList<>();
collectInOrder(root, result);
return result;
}
private static void collectInOrder(Node node, List<Integer> result) {
if (node == null) {
return;
}
collectInOrder(node.left, result);
result.add(node.key);
collectInOrder(node.right, result);
}
}编译并运行:
bash
javac BstInsertDemo.java
java BstInsertDemo预期输出
text
中序遍历: [1, 3, 4, 6, 7, 8, 10, 13, 14]
树高: 4
查找 7: true中序遍历结果严格递增,说明每个节点都满足“左子树键更小、右子树键更大”的约束。这里把单节点树的高度定义为 1,因此示例树高度为 4。
常见错误与练习
常见错误包括:比较后忘记更新 current,导致死循环;在发现空链接前就覆盖已有子节点,导致整棵子树丢失;没有定义重复键策略,使集合语义和计数语义混在一起。调试时可以同时检查中序遍历是否有序,以及插入前后的节点数量是否符合预期。
练习 1:把重复键策略改为在节点中维护 count,连续插入三个 6 后,要求树结构不增加节点,但键 6 的计数为 3。
练习 2:分别按升序和随机顺序插入 1 到 1000,输出两棵树的高度,并比较查找最后一个键时访问的节点数量。
本课总结
- 插入位置由连续比较唯一确定,算法只沿一条根到叶的路径前进。
- 插入时间为 ,树高决定实际性能,退化树的最坏成本为 。
- 中序遍历有序是验证二叉搜索树结构是否正确的直接方法。
下一课预告
下一课将学习“二叉搜索树删除”,重点处理叶节点、只有一个子节点和拥有两个子节点三种情况,并理解后继节点替换为什么能够保持搜索树性质。
按自己的节奏,确认真正理解。