可用数组实现AVL树：按完全二叉树索引规则存储节点，手动更新高度与平衡因子，通过值复制和索引重定位模拟旋转，支持LL/RR/LR/RL四种失衡调整。

不能用数组“直接实现”真正的 AVL 树，但可以用数组作为底层容器，手动模拟节点关系、高度更新与旋转逻辑——核心是把旋转理解为数据重排+索引重定位，而非指针改连。

数组如何映射二叉树结构

采用完全二叉树索引规则：根节点索引为 0；任意节点 i 的左子索引是 2*i + 1，右子索引是 2*i + 2，父节点索引是 (i−1)/2（整除）。数组每个位置存一个节点对象，至少包含 value 和 height 字段：

• 定义如：class Node { int val; int height; }
• 预分配空间：Node[] tree = new Node[1024];
• 插入时按 BST 规则找位置（从根开始比较，走左/右索引），不是填满数组，而是按逻辑路径写入有效索引

高度与平衡因子必须手动回溯更新

每次插入后，不能依赖递归，需从插入点向上循环跳转至根，逐个重算高度和平衡因子（bf = 左子树高度 − 右子树高度）：

• 设当前索引 cur = 插入位置；进入循环
• 计算 leftH = getHeight(2*cur+1)，rightH = getHeight(2*cur+2)（越界或空则返回 -1）
• 更新 tree[cur].height = 1 + Math.max(leftH, rightH)
• 计算 bf = leftH − rightH；若 |bf| > 1，触发旋转，并在旋转后立即重算相关节点高度
• 更新 cur = (cur−1)/2，继续向上，直到 cur

旋转本质是值+高度的交换与索引位移

以 RR 型（右子树过重，需左旋）为例，失衡节点 p 索引为 i，其右子 r 索引为 2*i+2：

• 左旋目标：r 上位为新父，p 变为其左子 → r 应移到位置 i，p 移到位置 2*i+1
• 操作步骤：
  • 暂存 p 节点：Node tmp = tree[i]
  • 把 r 数据复制到 i 位：tree[i] = new Node(tree[2*i+2].val, tree[2*i+2].height)
  • 把 p 数据复制到 r 的左子位（即 2*i+1）：tree[2*i+1] = tmp
  • 若原 r 有左子（索引 2*(2*i+2)+1），它现在要成为 p 的右子 → 复制到位置 2*(2*i+1)+2
• 注意：旋转只影响 p、r 及其直系子节点，这些节点的高度必须立刻重算

四种失衡类型对应旋转策略

判断依据是插入路径和各节点 bf 值，不依赖指针方向，而看索引相对位置：

• LL 型：p 的 bf > 1，且其左子 l 的 bf ≥ 0 → 对 p 执行右旋（l 上位，p 变右子）
• RR 型：p 的 bf
• LR 型：p 的 bf > 1，但其左子 l 的 bf
• RL 型：p 的 bf 0 → 先对 r 右旋，再对 p 左旋