目录
一、主要任务
二、主要内容
1. 什么是二叉搜索树（BST）？
2. BST的基本操作实现
2.1 节点定义
2.2 插入操作
2.3 查找操作
2.4 删除操作
3. 为什么需要AVL树？
4. AVL树的核心概念
4.1 节点定义（带高度）
4.2 获取高度和平衡因子的辅助方法
4.3 更新高度
5. AVL树的四种旋转
5.1 右旋（LL情况）
5.2 左旋（RR情况）
5.3 左右旋（LR情况）
5.4 右左旋（RL情况）
6. AVL树的插入操作
6.1 删除操作（简略）
7. 对比BST和AVL的树高变化
7.1 计算树高的方法
7.2 测试代码
8. 调试旋转：通过具体示例观察
9. 完整代码示例
10. 总结
一、主要任务
1. 实现BST的增、删、查。
2. 理解AVL树的平衡因子与旋转（左旋、右旋）。
3、手写BST和AVL树，调试旋转操作，对比平衡前后的树高变化。
二、主要内容
在数据结构中，二叉搜索树（BST）是最基础的树形结构之一，而AVL树（平衡二叉树）则是它的“升级版”——通过自动平衡机制，避免了BST在最坏情况下退化成链表，保证了高效的查找性能。本文将带领你从零开始，用Java手写BST和AVL树，并通过实际代码调试旋转操作，直观对比平衡前后的树高变化。
1. 什么是二叉搜索树（BST）？
二叉搜索树是一棵二叉树，满足以下性质：
-
每个节点有一个键（key）和值（value），通常键是唯一的。
-
左子树所有节点的键都小于根节点的键。
-
右子树所有节点的键都大于根节点的键。
-
左右子树也分别是二叉搜索树。
这个性质使得我们可以在O(log n)（平均）时间内完成查找、插入和删除。但最坏情况下，如果插入的数据是有序的，BST会退化成一条链表，操作复杂度变为O(n)。这就是我们需要平衡树的理由。
2. BST的基本操作实现
2.1 节点定义
每个节点包含键、值、左子节点引用、右子节点引用。
class BSTNode {
int key;
String value; // 这里用String作为值类型，方便演示
BSTNode left, right;
public BSTNode(int key, String value) {
this.key = key;
this.value = value;
left = right = null;
}
}
2.2 插入操作
插入操作递归地进行：如果当前节点为空，直接创建新节点；如果key小于当前节点，插入左子树；如果大于，插入右子树；如果等于，更新值。
public BSTNode insert(BSTNode node, int key, String value) {
if (node == null) {
return new BSTNode(key, value);
}
if (key < node.key) {
node.left = insert(node.left, key, value);
} else if (key > node.key) {
node.right = insert(node.right, key, value);
} else {
// key相等，更新值
node.value = value;
}
return node;
}
2.3 查找操作
查找也是递归的：从根开始，如果key等于当前节点，返回；如果小于，去左子树找；如果大于，去右子树找；如果没找到，返回null。
public String search(BSTNode node, int key) {
if (node == null) return null;
if (key < node.key) return search(node.left, key);
else if (key > node.key) return search(node.right, key);
else return node.value;
}
2.4 删除操作
删除是BST中最复杂的操作，需要分三种情况：
-
叶子节点：直接删除。
-
有一个孩子：用孩子替换该节点。
-
有两个孩子：找到右子树中的最小节点（或左子树中的最大节点）来替换当前节点，然后删除那个最小节点。
public BSTNode delete(BSTNode node, int key) {
if (node == null) return null;
if (key < node.key) {
node.left = delete(node.left, key);
} else if (key > node.key) {
node.right = delete(node.right, key);
} else {
// 找到要删除的节点
if (node.left == null) {
// 只有右孩子或没有孩子
return node.right;
} else if (node.right == null) {
// 只有左孩子
return node.left;
} else {
// 有两个孩子，找右子树的最小节点
BSTNode minNode = findMin(node.right);
// 用最小节点的键值覆盖当前节点
node.key = minNode.key;
node.value = minNode.value;
// 删除右子树中的那个最小节点
node.right = delete(node.right, minNode.key);
}
}
return node;
}
private BSTNode findMin(BSTNode node) {
while (node.left != null) node = node.left;
return node;
}
3. 为什么需要AVL树？
当插入有序数据时，BST会变得不平衡。例如依次插入1,2,3,4,5，树会变成一条右斜链，查找5需要比较5次，效率O(n)。为了解决这个问题，我们引入自平衡二叉搜索树，AVL树是其中一种。
4. AVL树的核心概念
AVL树是每个节点左右子树高度差的绝对值不超过1的二叉搜索树。这个高度差称为平衡因子：
平衡因子 = 左子树高度 – 右子树高度
平衡因子只能是 -1、0、1。当插入或删除导致平衡因子绝对值大于1时，需要通过旋转来恢复平衡。
4.1 节点定义（带高度）
在BST节点基础上增加一个height属性，用于计算平衡因子。
class AVLNode {
int key;
String value;
AVLNode left, right;
int height; // 当前节点的高度（从该节点到叶子的最长路径）
public AVLNode(int key, String value) {
this.key = key;
this.value = value;
left = right = null;
height = 1; // 新节点初始高度为1
}
}
4.2 获取高度和平衡因子的辅助方法
private int height(AVLNode node) {
return node == null ? 0 : node.height;
}
private int getBalance(AVLNode node) {
return node == null ? 0 : height(node.left) – height(node.right);
}
4.3 更新高度
当节点左右子树变化后，需要重新计算高度：
private void updateHeight(AVLNode node) {
node.height = 1 + Math.max(height(node.left), height(node.right));
}
5. AVL树的四种旋转
当插入或删除导致节点平衡因子变为2或-2时，我们需要旋转。旋转分为四种情况：
5.1 右旋（LL情况）
当节点左子树的左子树插入导致不平衡（左左情况）。如下图（用文字描述）：
y (平衡因子+2) x / \\ / \\ x T3 右旋 z y / \\ –> / / \\ z T2 T1 T2 T3 / T1
代码实现：
private AVLNode rotateRight(AVLNode y) {
AVLNode x = y.left;
AVLNode T2 = x.right;
// 旋转
x.right = y;
y.left = T2;
// 更新高度
updateHeight(y);
updateHeight(x);
return x; // 新的根
}
5.2 左旋（RR情况）
节点右子树的右子树插入导致不平衡（右右情况）。
x (平衡因子-2) y / \\ / \\ T1 y 左旋 x z / \\ –> / \\ \\ T2 z T1 T2 T3 \\ T3
private AVLNode rotateLeft(AVLNode x) {
AVLNode y = x.right;
AVLNode T2 = y.left;
y.left = x;
x.right = T2;
updateHeight(x);
updateHeight(y);
return y;
}
5.3 左右旋（LR情况）
节点左子树的右子树插入导致不平衡。需要先左旋左子节点，再右旋当前节点。
z / \\ x T4 / \\ T1 y / \\ T2 T3
步骤：
对x进行左旋（变成LL情况）
对z进行右旋
代码：
private AVLNode rotateLR(AVLNode z) {
z.left = rotateLeft(z.left);
return rotateRight(z);
}
5.4 右左旋（RL情况）
节点右子树的左子树插入导致不平衡。先右旋右子节点，再左旋当前节点。
private AVLNode rotateRL(AVLNode z) {
z.right = rotateRight(z.right);
return rotateLeft(z);
}
6. AVL树的插入操作
插入过程与BST类似，但插入后需要回溯更新高度，并检查平衡因子，必要时旋转。
public AVLNode insert(AVLNode node, int key, String value) {
// 1. 普通BST插入
if (node == null) {
return new AVLNode(key, value);
}
if (key < node.key) {
node.left = insert(node.left, key, value);
} else if (key > node.key) {
node.right = insert(node.right, key, value);
} else {
node.value = value; // 更新
return node;
}
// 2. 更新当前节点的高度
updateHeight(node);
// 3. 获取平衡因子
int balance = getBalance(node);
// 4. 判断是否需要旋转
// 左左情况
if (balance > 1 && key < node.left.key) {
return rotateRight(node);
}
// 右右情况
if (balance < -1 && key > node.right.key) {
return rotateLeft(node);
}
// 左右情况
if (balance > 1 && key > node.left.key) {
return rotateLR(node);
}
// 右左情况
if (balance < -1 && key < node.right.key) {
return rotateRL(node);
}
return node;
}
6.1 删除操作（简略）
AVL的删除类似BST，但删除后需要从删除节点的父节点开始向上回溯，更新高度并旋转。由于篇幅，这里不展开完整代码，但思路是一致的：找到删除节点、处理三种情况、然后回溯调整。
7. 对比BST和AVL的树高变化
为了直观感受平衡的效果，我们可以写一个测试程序：向BST和AVL插入相同的序列（比如顺序插入1到10），然后计算树高。
7.1 计算树高的方法
public int getHeight(BSTNode node) {
if (node == null) return 0;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
7.2 测试代码
public class TreeDemo {
public static void main(String[] args) {
// 测试BST
BSTNode bstRoot = null;
BST bst = new BST(); // 假设有BST类封装了操作
for (int i = 1; i <= 10; i++) {
bstRoot = bst.insert(bstRoot, i, "val" + i);
}
System.out.println("BST树高: " + getBSTHeight(bstRoot)); // 应该是10
// 测试AVL
AVLNode avlRoot = null;
AVL avl = new AVL();
for (int i = 1; i <= 10; i++) {
avlRoot = avl.insert(avlRoot, i, "val" + i);
}
System.out.println("AVL树高: " + getAVLHeight(avlRoot)); // 应该是4（log2(10)≈4）
}
}
输出结果：
BST树高: 10
AVL树高: 4
可以看到，AVL树通过旋转保持了高度平衡，使得树高从10降到了4，查找效率大大提高。
8. 调试旋转：通过具体示例观察
让我们用一个简单例子来演示旋转过程。假设我们向空AVL树依次插入3,2,1。
插入3：
-
树：3 (高度1)
插入2：
-
插入后：3的左子为2
-
3的平衡因子 = 左高1 – 右高0 = 1，平衡
-
树：
3 / 2
插入1：
-
先插入到2的左子：
3
/
2
/
1
-
更新高度：节点1高1，节点2高2，节点3高3。
-
节点2的平衡因子 = 1-0=1，平衡。
-
节点3的平衡因子 = 2-0=2，不平衡！且是LL情况（左子树的左子树插入），需要右旋。
右旋过程：
-
以节点3为y，左子节点2为x，T2是x的右子树（null）。
-
执行rotateRight(3)：
-
x.right = y -> 2的右子指向3
-
y.left = T2 -> 3的左子置空
-
-
返回x（2）作为新根。
旋转后树：
text
2
/ \\
1 3
平衡因子均为0，高度2。
通过这个例子，我们可以逐步调试代码，打印每次旋转前后的树结构和高度，加深理解。
9. 完整代码示例
下面给出一个简化的AVL树完整实现，包含插入和高度计算，并附有注释。
class AVLTree {
private AVLNode root;
private int height(AVLNode node) {
return node == null ? 0 : node.height;
}
private void updateHeight(AVLNode node) {
node.height = 1 + Math.max(height(node.left), height(node.right));
}
private int getBalance(AVLNode node) {
return node == null ? 0 : height(node.left) – height(node.right);
}
private AVLNode rotateRight(AVLNode y) {
AVLNode x = y.left;
AVLNode T2 = x.right;
x.right = y;
y.left = T2;
updateHeight(y);
updateHeight(x);
return x;
}
private AVLNode rotateLeft(AVLNode x) {
AVLNode y = x.right;
AVLNode T2 = y.left;
y.left = x;
x.right = T2;
updateHeight(x);
updateHeight(y);
return y;
}
private AVLNode rotateLR(AVLNode z) {
z.left = rotateLeft(z.left);
return rotateRight(z);
}
private AVLNode rotateRL(AVLNode z) {
z.right = rotateRight(z.right);
return rotateLeft(z);
}
public void insert(int key, String value) {
root = insert(root, key, value);
}
private AVLNode insert(AVLNode node, int key, String value) {
if (node == null) {
return new AVLNode(key, value);
}
if (key < node.key) {
node.left = insert(node.left, key, value);
} else if (key > node.key) {
node.right = insert(node.right, key, value);
} else {
node.value = value;
return node;
}
updateHeight(node);
int balance = getBalance(node);
// 左左
if (balance > 1 && key < node.left.key) {
return rotateRight(node);
}
// 右右
if (balance < -1 && key > node.right.key) {
return rotateLeft(node);
}
// 左右
if (balance > 1 && key > node.left.key) {
return rotateLR(node);
}
// 右左
if (balance < -1 && key < node.right.key) {
return rotateRL(node);
}
return node;
}
public int getHeight() {
return height(root);
}
// 中序遍历等可添加
}
10. 总结
通过本文，我们：
-
实现了BST的基本操作（插入、查找、删除）。
-
理解了AVL树的平衡因子和四种旋转。
-
用Java手写了AVL树，并测试了插入时的自动平衡。
-
对比了BST和AVL在相同输入下的树高，直观感受平衡的重要性。
