数组实现平衡二叉树与旋转变量节点实战

本文深入探讨了如何巧妙地利用数组而非传统指针结构来模拟实现AVL平衡二叉树，揭示了在完全二叉树索引规则下通过值复制、索引重定位和手动高度回溯更新来精准复现LL/RR/LR/RL四种旋转逻辑的本质——旋转并非指针重连，而是数据与位置的协同重构；这种“数组模拟法”虽不改变底层存储的静态特性，却以清晰可控的方式实现了动态平衡的核心机制，为理解AVL原理、嵌入式场景或内存受限环境下的树结构实现提供了极具启发性的实践路径。

不能用数组“直接实现”真正的 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 < 0

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

以 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 < −1，且其右子 r 的 bf ≤ 0 → 对 p 执行左旋
• LR 型：p 的 bf > 1，但其左子 l 的 bf < 0 → 先对 l 左旋，再对 p 右旋
• RL 型：p 的 bf < −1，但其右子 r 的 bf > 0 → 先对 r 右旋，再对 p 左旋

本篇关于《数组实现平衡二叉树与旋转变量节点实战》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！