二叉搜索树与平衡树
二叉搜索树是一种特殊的二叉树，它能保持元素的有序性，并提供高效的查找、插入和删除操作。
二叉搜索树 (BST)
核心性质
二叉搜索树具有以下关键性质：
- 若左子树不为空，则左子树上所有节点的值均小于根节点的值
- 若右子树不为空，则右子树上所有节点的值均大于根节点的值
- 左右子树也分别为二叉搜索树
这些性质带来了一个重要推论：BST的中序遍历序列是严格递增的。这个特性让我们能够在 时间内得到有序序列，也常用于验证一棵树是否为BST。
为什么需要BST？
假设我们需要维护一个动态集合，支持以下操作：
- 查找某个元素是否存在
- 插入新元素
- 删除已有元素
使用数组实现时，查找需要 ，有序插入也需要 。而BST可以将这些操作优化到 ，前提是树保持相对平衡。
核心操作实现
查找操作
查找从根节点开始，利用BST性质快速缩小搜索范围：
public TreeNode search(TreeNode root, int val) {
// 空树或找到目标
if (root == null || root.val == val) {
return root;
}
// 目标值小于当前节点，向左子树查找
if (val < root.val) {
return search(root.left, val);
}
// 目标值大于当前节点，向右子树查找
return search(root.right, val);
}
时间复杂度：平均 ，最坏 （树退化为链表时）。
插入操作
插入时需要找到合适的位置，保持BST性质：
public TreeNode insert(TreeNode root, int val) {
// 找到空位置，创建新节点
if (root == null) {
return new TreeNode(val);
}
// 递归插入到正确的子树
if (val < root.val) {
root.left = insert(root.left, val);
} else if (val > root.val) {
root.right = insert(root.right, val);
}
// val已存在，不插入（BST通常不允许重复）
return root;
}
删除操作
删除是最复杂的操作，需要考虑三种情况：
- 叶子节点：直接删除
- 只有一个子节点：用子节点替换被删除节点
- 有两个子节点：用前驱（左子树最大值）或后继（右子树最小值）替换
public TreeNode delete(TreeNode root, int val) {
if (root == null) return null;
// 找到要删除的节点
if (val < root.val) {
root.left = delete(root.left, val);
} else if (val > root.val) {
root.right = delete(root.right, val);
} else {
// 情况1和2：只有一个子节点或没有子节点
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 情况3：两个子节点都存在
// 找到后继节点（右子树的最小值）
TreeNode successor = findMin(root.right);
root.val = successor.val;
// 删除后继节点
root.right = delete(root.right, successor.val);
}
return root;
}
private TreeNode findMin(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
BST的缺陷
当插入有序序列（如1, 2, 3, 4, 5）时，BST会退化为链表，所有操作的时间复杂度都会变成 。这就是为什么需要平衡树。
平衡二叉树 (AVL树)
AVL树是最早发明的自平衡二叉搜索树，由 Adelson-Velsky 和 Landis 在1962年提出。它通过严格的平衡条件，保证所有操作的时间复杂度始终为 。
平衡因子
每个节点都有一个平衡因子（Balance Factor），定义为：
AVL树要求任意节点的平衡因子满足 ，即左右子树高度差不超过1。当插入或删除操作导致某个节点的平衡因子超出这个范围时，需要通过旋转来恢复平衡。
四种旋转方式
当平衡被破坏时，根据插入位置的不同，需要采用不同的旋转策略。
LL型：右单旋
场景：在左子树的左子树插入节点，导致左子树过高。
插入前（平衡） 插入后（失衡） 右旋后（恢复平衡）
2 2 1
/ \ / \ / \
1 3 → 1 3 → 0 2
/ / / \
0 0 0' 3
0'（新插入）
右旋操作：将左子节点提升为新的根节点，原根节点成为新根节点的右子节点。
// 右旋（用于LL型失衡）
private TreeNode rotateRight(TreeNode y) {
TreeNode x = y.left; // x成为新的根
TreeNode T2 = x.right; // 保存x的右子树
// 执行旋转
x.right = y; // y成为x的右子节点
y.left = T2; // T2成为y的左子树
// 更新高度（先更新y，因为y现在是子节点）
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x; // 返回新的根节点
}
RR型：左单旋
场景：在右子树的右子树插入节点，导致右子树过高。这是LL型的镜像情况。
插入前（平衡） 插入后（失衡） 左旋后（恢复平衡）
1 1 2
/ \ / \ / \
0 2 → 0 2 → 1 3
\ \ / \
3 3 0 3'
3'（新插入）
// 左旋（用于RR型失衡）
private TreeNode rotateLeft(TreeNode x) {
TreeNode y = x.right; // y成为新的根
TreeNode T2 = y.left; // 保存y的左子树
// 执行旋转
y.left = x; // x成为y的左子节点
x.right = T2; // T2成为x的右子树
// 更新高度
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y; // 返回新的根节点
}
LR型：先左旋后右旋
场景：在左子树的右子树插入节点。单次旋转无法恢复平衡，需要两次旋转。
插入后（失衡） 先对1左旋 再对3右旋
3 3 2
/ \ / \ / \
1 4 → 2 4 → 1 3
/ \ / / \
0 2 1 0 4
（新插入） /
0
理解：先把"弯"的部分"拉直"（左旋），然后再进行标准的右旋。
// LR型：先左旋后右旋
private TreeNode rotateLeftRight(TreeNode node) {
node.left = rotateLeft(node.left); // 先对左子节点左旋
return rotateRight(node); // 再对当前节点右旋
}
RL型：先右旋后左旋
场景：在右子树的左子树插入节点。这是LR型的镜像情况。
插入后（失衡） 先对3右旋 再对1左旋
1 1 2
/ \ / \ / \
0 3 → 0 2 → 1 3
/ \ \ / \
2 4 3 0 4
（新插入） \
4
// RL型：先右旋后左旋
private TreeNode rotateRightLeft(TreeNode node) {
node.right = rotateRight(node.right); // 先对右子节点右旋
return rotateLeft(node); // 再对当前节点左旋
}
判断旋转类型
关键在于找到第一个失衡的节点，然后检查其子节点的平衡因子：
private TreeNode rebalance(TreeNode node) {
int balance = getBalance(node);
// LL型：左子树高，且左子节点的左子树更高或相等
if (balance > 1 && getBalance(node.left) >= 0) {
return rotateRight(node);
}
// RR型：右子树高，且右子节点的右子树更高或相等
if (balance < -1 && getBalance(node.right) <= 0) {
return rotateLeft(node);
}
// LR型：左子树高，但左子节点的右子树更高
if (balance > 1 && getBalance(node.left) < 0) {
return rotateLeftRight(node);
}
// RL型：右子树高，但右子节点的左子树更高
if (balance < -1 && getBalance(node.right) > 0) {
return rotateRightLeft(node);
}
return node; // 已经平衡
}
private int getBalance(TreeNode node) {
if (node == null) return 0;
return height(node.left) - height(node.right);
}
private int height(TreeNode node) {
if (node == null) return 0;
return node.height;
}
AVL树完整实现
public class AVLTree {
private class TreeNode {
int val;
int height; // 节点高度，用于计算平衡因子
TreeNode left, right;
TreeNode(int val) {
this.val = val;
this.height = 1;
}
}
private TreeNode root;
// 插入操作
public void insert(int val) {
root = insert(root, val);
}
private TreeNode insert(TreeNode node, int val) {
// 标准BST插入
if (node == null) {
return new TreeNode(val);
}
if (val < node.val) {
node.left = insert(node.left, val);
} else if (val > node.val) {
node.right = insert(node.right, val);
} else {
return node; // 不允许重复值
}
// 更新高度
node.height = 1 + Math.max(height(node.left), height(node.right));
// 重新平衡
return rebalance(node);
}
// 删除操作
public void delete(int val) {
root = delete(root, val);
}
private TreeNode delete(TreeNode node, int val) {
// 标准BST删除
if (node == null) return null;
if (val < node.val) {
node.left = delete(node.left, val);
} else if (val > node.val) {
node.right = delete(node.right, val);
} else {
if (node.left == null) return node.right;
if (node.right == null) return node.left;
TreeNode successor = findMin(node.right);
node.val = successor.val;
node.right = delete(node.right, successor.val);
}
// 更新高度
node.height = 1 + Math.max(height(node.left), height(node.right));
// 重新平衡
return rebalance(node);
}
// ... 前面定义的旋转和辅助方法
}
AVL树 vs 红黑树
| 特性 | AVL树 | 红黑树 |
|---|---|---|
| 平衡条件 | 严格：高度差 ≤ 1 | 宽松：最长路径不超过最短路径的2倍 |
| 查找效率 | 更高（树更矮） | 略低 |
| 插入/删除 | 更多旋转操作 | 较少旋转操作 |
| 适用场景 | 查找密集型 | 插入删除频繁 |
| 工业应用 | 数据库索引 | Java TreeMap, C++ std::map |
实战练习
- LeetCode 98：验证二叉搜索树（利用中序遍历的递增性质）
- LeetCode 700：二叉搜索树中的搜索
- LeetCode 450：删除二叉搜索树中的节点
- LeetCode 110：平衡二叉树（判断是否为AVL树）
- LeetCode 108：将有序数组转换为平衡BST
- 手写实现：完整实现AVL树的四种旋转
延伸阅读
- 红黑树：工业界最常用的平衡BST，Java的
TreeMap和HashMap（链表转树后）都使用它 - B树与B+树：磁盘友好的平衡树，广泛用于数据库索引
- 跳表：另一种 查找的数据结构，Redis 的有序集合使用它