平衡二叉树（AVL）的核心是通过旋转操作维持树的高度平衡，每个节点的左右子树高度差不超过1。除了常见的对象节点实现方式，我们也可以用数组模拟节点存储，通过下标关联节点间的父子关系，这种方式更适合理解树结构的底层存储逻辑。
数组模拟AVL树的节点存储设计
用数组模拟AVL树时，每个节点需要存储三个核心信息：节点值、左子节点下标、右子节点下标，同时还需要记录节点的高度用于平衡判断。我们可以定义三个数组分别存储这些信息，再用一个变量记录当前可用的最小下标，或者维护一个根节点下标表示树的根。
假设我们用以下数组结构实现节点存储：
- values数组：存储节点的实际值，初始值可以设为-1表示空节点
- left数组：存储节点的左子节点在数组中的下标，-1表示无左子节点
- right数组：存储节点的右子节点在数组中的下标，-1表示无右子节点
- heights数组：存储节点的高度，空节点高度为0，叶子节点高度为1
- root变量：记录当前树的根节点在数组中的下标
- size变量：记录当前数组中已使用的节点数量，新节点插入时分配到size位置，之后size自增
基础工具方法实现
首先需要实现几个基础方法，包括获取节点高度、计算平衡因子、创建新节点等，这些是后续旋转和插入操作的基础。
// 定义数组容量，可根据实际需求调整
private static final int CAPACITY = 100;
// 存储节点值，-1表示空节点
private static int[] values = new int[CAPACITY];
// 存储左子节点下标，-1表示无左子节点
private static int[] left = new int[CAPACITY];
// 存储右子节点下标，-1表示无右子节点
private static int[] right = new int[CAPACITY];
// 存储节点高度
private static int[] heights = new int[CAPACITY];
// 根节点下标
private static int root = -1;
// 已使用节点数量，新节点分配到该位置
private static int size = 0;
// 初始化数组，所有位置默认值设为-1
static {
for (int i = 0; i < CAPACITY; i++) {
values[i] = -1;
left[i] = -1;
right[i] = -1;
heights[i] = 0;
}
}
// 获取节点高度，传入节点下标，空节点返回0
private static int getHeight(int idx) {
if (idx == -1 || values[idx] == -1) {
return 0;
}
return heights[idx];
}
// 计算节点的平衡因子：左子树高度 - 右子树高度
private static int getBalanceFactor(int idx) {
if (idx == -1 || values[idx] == -1) {
return 0;
}
return getHeight(left[idx]) - getHeight(right[idx]);
}
// 创建新节点，返回节点在数组中的下标
private static int createNode(int val) {
int idx = size;
size++;
values[idx] = val;
left[idx] = -1;
right[idx] = -1;
heights[idx] = 1;
return idx;
}
// 更新节点高度，在旋转或插入删除后调用
private static void updateHeight(int idx) {
if (idx == -1 || values[idx] == -1) {
return;
}
int leftH = getHeight(left[idx]);
int rightH = getHeight(right[idx]);
heights[idx] = Math.max(leftH, rightH) + 1;
}
AVL树四种旋转逻辑实现
AVL树的旋转分为四种情况：右单旋（左左失衡）、左单旋（右右失衡）、左右双旋（左右失衡）、右左双旋（右左失衡），下面逐一实现这些旋转逻辑，旋转过程中需要调整对应节点的左右子节点下标，并更新节点高度。
右单旋（处理左左失衡）
当节点的平衡因子大于1，且左子节点的平衡因子大于等于0时，触发右单旋。旋转后原左子节点成为新的根，原节点成为新根的右子节点，原左子节点的右子树成为原节点的左子树。
// 右单旋，传入失衡节点下标，返回旋转后的新根节点下标
private static int rightRotate(int y) {
int x = left[y];
int t = right[x];
// 执行旋转
right[x] = y;
left[y] = t;
// 更新节点高度，先更新子节点再更新父节点
updateHeight(y);
updateHeight(x);
return x;
}
左单旋（处理右右失衡）
当节点的平衡因子小于-1，且右子节点的平衡因子小于等于0时，触发左单旋。旋转后原右子节点成为新的根，原节点成为新根的左子节点，原右子节点的左子树成为原节点的右子树。
// 左单旋，传入失衡节点下标，返回旋转后的新根节点下标
private static int leftRotate(int x) {
int y = right[x];
int t = left[y];
// 执行旋转
left[y] = x;
right[x] = t;
// 更新节点高度
updateHeight(x);
updateHeight(y);
return y;
}
左右双旋（处理左右失衡）
当节点的平衡因子大于1，且左子节点的平衡因子小于0时，需要先对左子节点做左单旋，再对原节点做右单旋。
// 左右双旋，先左旋左子节点，再右旋当前节点
private static int leftRightRotate(int idx) {
left[idx] = leftRotate(left[idx]);
return rightRotate(idx);
}
右左双旋（处理右左失衡）
当节点的平衡因子小于-1，且右子节点的平衡因子大于0时，需要先对右子节点做右单旋，再对原节点做左单旋。
// 右左双旋，先右旋右子节点，再左旋当前节点
private static int rightLeftRotate(int idx) {
right[idx] = rightRotate(right[idx]);
return leftRotate(idx);
}
插入操作的完整实现
插入操作需要先按照二叉查找树的规则找到插入位置，创建新节点后，回溯更新节点高度并检查平衡，根据失衡类型调用对应的旋转方法，最终更新根节点下标。
// 插入节点，对外调用的方法
private static void insert(int val) {
root = insertNode(root, val);
}
// 递归插入节点，返回当前子树的根节点下标
private static int insertNode(int idx, int val) {
// 当前位置为空，创建新节点
if (idx == -1 || values[idx] == -1) {
return createNode(val);
}
if (val < values[idx]) {
// 插入到左子树
left[idx] = insertNode(left[idx], val);
} else if (val > values[idx]) {
// 插入到右子树
right[idx] = insertNode(right[idx], val);
} else {
// 值已存在，AVL树通常不允许重复值，直接返回
return idx;
}
// 更新当前节点高度
updateHeight(idx);
// 计算平衡因子，判断是否需要旋转
int balance = getBalanceFactor(idx);
// 左左失衡，右单旋
if (balance > 1 && val < values[left[idx]]) {
return rightRotate(idx);
}
// 右右失衡，左单旋
if (balance < -1 && val > values[right[idx]]) {
return leftRotate(idx);
}
// 左右失衡，左右双旋
if (balance > 1 && val > values[left[idx]]) {
return leftRightRotate(idx);
}
// 右左失衡，右左双旋
if (balance < -1 && val < values[right[idx]]) {
return rightLeftRotate(idx);
}
// 无需旋转，返回当前节点下标
return idx;
}
测试验证
我们可以编写一个简单的测试方法，插入一组数值后，检查根节点和各个节点的高度是否符合AVL树的平衡要求。
public static void main(String[] args) {
// 插入测试数据
int[] testVals = {10, 20, 30, 40, 50, 25};
for (int val : testVals) {
insert(val);
}
// 输出根节点信息和高度
System.out.println("根节点值：" + values[root]);
System.out.println("根节点高度：" + heights[root]);
System.out.println("根节点左子节点值：" + (left[root] == -1 ? -1 : values[left[root]]));
System.out.println("根节点右子节点值：" + (right[root] == -1 ? -1 : values[right[root]]));
System.out.println("左子节点高度：" + (left[root] == -1 ? 0 : heights[left[root]]));
System.out.println("右子节点高度：" + (right[root] == -1 ? 0 : heights[right[root]]));
}
上述测试代码插入10、20、30、40、50、25后，最终根节点会经过旋转调整，左右子树高度差不超过1，符合AVL树的平衡特性。通过数组模拟的方式，我们可以更直观地看到节点之间的下标关联，理解AVL树旋转时节点指向的变化逻辑。