平衡二叉搜索树是在二叉搜索树的基础上增加了平衡约束的数据结构，二叉搜索树本身满足左子树所有节点值小于根节点、右子树所有节点值大于根节点的特性，但普通二叉搜索树在有序插入时容易退化为链表，导致操作效率下降。平衡二叉搜索树通过限制每个节点的左右子树高度差，保证树的整体高度维持在较低水平，从而让各项操作的时间复杂度稳定在对数级别。
平衡二叉搜索树的核心特性
平衡二叉搜索树首先需要满足二叉搜索树的所有性质，在此基础上还要满足平衡条件：对于树中的每一个节点，其左子树和右子树的高度差的绝对值不超过某个固定阈值。不同的平衡二叉搜索树实现阈值不同，AVL树的阈值设定为1，也就是任意节点的左右子树高度差只能是-1、0、1这三种情况。
这种平衡特性带来的直接好处是树的高度不会超过O(log n)，其中n是节点总数，因此查找、插入、删除操作都可以在O(log n)时间内完成，比普通二叉搜索树的最坏情况O(n)要高效很多。
AVL树的基本概念
AVL树是最早被发明的自平衡二叉搜索树，它以发明者Adelson-Velsky和Landis的名字命名。AVL树中每个节点都会存储一个平衡因子，平衡因子的计算方式是左子树高度减去右子树高度，根据AVL树的规则，所有节点的平衡因子只能是-1、0、1。
当插入或删除节点导致某个节点的平衡因子超出这个范围时，就需要通过旋转操作调整树的结构，让所有节点的平衡因子重新回到合法区间，这个过程就是AVL树的平衡调整。
AVL树的四种旋转场景
根据失衡节点的平衡因子以及其子节点的平衡因子情况，AVL树的旋转可以分为四种类型，分别是左旋、右旋、左右旋、右左旋。
1. 右旋（LL型失衡）
当失衡节点的平衡因子为2，且其左子节点的平衡因子为1时，属于LL型失衡，此时需要对失衡节点进行右旋操作。右旋的核心逻辑是将失衡节点的左子节点提升为新的根节点，原失衡节点变为新根节点的右子节点，同时调整相关子树的归属。
假设失衡节点为node，其左子节点为left，右旋的步骤如下：
- 将left的右子树作为node的左子树
- 将node作为left的右子树
- 更新node和left的高度
- 返回left作为新的子树根节点
以下是右旋的代码示例：
// 定义AVL树节点结构
class AVLNode {
int val;
int height;
AVLNode left;
AVLNode right;
AVLNode(int val) {
this.val = val;
this.height = 1; // 新节点初始高度为1
}
}
// 获取节点高度，空节点高度为0
int getHeight(AVLNode node) {
if (node == null) {
return 0;
}
return node.height;
}
// 更新节点高度，高度为左右子树最大高度加1
void updateHeight(AVLNode node) {
if (node != null) {
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
}
// 右旋操作，处理LL型失衡
AVLNode rightRotate(AVLNode node) {
AVLNode left = node.left;
AVLNode leftRight = left.right;
// 调整结构
left.right = node;
node.left = leftRight;
// 更新高度，先更新子节点再更新父节点
updateHeight(node);
updateHeight(left);
return left; // 返回新的根节点
}
2. 左旋（RR型失衡）
当失衡节点的平衡因子为-2，且其右子节点的平衡因子为-1时，属于RR型失衡，此时需要对失衡节点进行左旋操作。左旋的逻辑和右旋对称，将失衡节点的右子节点提升为新的根节点，原失衡节点变为新根节点的左子节点，同时调整相关子树的归属。
左旋的步骤如下：
- 将right的左子树作为node的右子树
- 将node作为right的左子树
- 更新node和right的高度
- 返回right作为新的子树根节点
左旋的代码示例：
// 左旋操作，处理RR型失衡
AVLNode leftRotate(AVLNode node) {
AVLNode right = node.right;
AVLNode rightLeft = right.left;
// 调整结构
right.left = node;
node.right = rightLeft;
// 更新高度
updateHeight(node);
updateHeight(right);
return right; // 返回新的根节点
}
3. 左右旋（LR型失衡）
当失衡节点的平衡因子为2，且其左子节点的平衡因子为-1时，属于LR型失衡。这种情况无法单次旋转解决，需要先对失衡节点的左子节点进行左旋，将结构转换为LL型，再对失衡节点进行右旋。
左右旋的步骤如下：
- 对失衡节点的左子节点执行左旋操作
- 对失衡节点执行右旋操作
代码示例：
// 左右旋操作，处理LR型失衡
AVLNode leftRightRotate(AVLNode node) {
// 先对左子节点左旋
node.left = leftRotate(node.left);
// 再对当前节点右旋
return rightRotate(node);
}
4. 右左旋（RL型失衡）
当失衡节点的平衡因子为-2，且其右子节点的平衡因子为1时，属于RL型失衡。这种情况需要先对失衡节点的右子节点进行右旋，将结构转换为RR型，再对失衡节点进行左旋。
右左旋的步骤如下：
- 对失衡节点的右子节点执行右旋操作
- 对失衡节点执行左旋操作
代码示例：
// 右左旋操作，处理RL型失衡
AVLNode rightLeftRotate(AVLNode node) {
// 先对右子节点右旋
node.right = rightRotate(node.right);
// 再对当前节点左旋
return leftRotate(node);
}
AVL树插入操作的平衡调整
插入节点后，需要从插入节点向上回溯更新每个祖先节点的高度，并检查平衡因子是否合法。一旦发现失衡节点，就根据失衡类型选择对应的旋转操作进行调整。
插入操作的完整逻辑如下：
// 获取节点平衡因子
int getBalance(AVLNode node) {
if (node == null) {
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
// AVL树插入节点
AVLNode insert(AVLNode root, int val) {
// 1. 按照二叉搜索树规则插入新节点
if (root == null) {
return new AVLNode(val);
}
if (val < root.val) {
root.left = insert(root.left, val);
} else if (val > root.val) {
root.right = insert(root.right, val);
} else {
// AVL树通常不允许重复值，直接返回
return root;
}
// 2. 更新当前节点高度
updateHeight(root);
// 3. 计算平衡因子，检查是否失衡
int balance = getBalance(root);
// LL型失衡
if (balance > 1 && val < root.left.val) {
return rightRotate(root);
}
// RR型失衡
if (balance < -1 && val > root.right.val) {
return leftRotate(root);
}
// LR型失衡
if (balance > 1 && val > root.left.val) {
return leftRightRotate(root);
}
// RL型失衡
if (balance < -1 && val < root.right.val) {
return rightLeftRotate(root);
}
// 没有失衡，直接返回当前节点
return root;
}
旋转操作的时间复杂度分析
AVL树的旋转操作都是局部调整，每次旋转只涉及常数个节点的指针修改和高度更新，因此单次旋转的时间复杂度是O(1)。插入或删除操作中最多只需要两次旋转就可以让整棵树恢复平衡，因此平衡调整的整体开销很低，不会影响到AVL树操作的对数级时间复杂度优势。
和普通二叉搜索树相比，AVL树通过旋转操作额外付出的维护成本很低，却换来了稳定的操作性能，因此在需要频繁查找、对性能稳定性要求高的场景中，AVL树是非常合适的数据结构选择。