C++实现平衡二叉树AVL的高度自平衡 _ 节点旋转逻辑代码【源码】-C++-PHP中文网

avl树插入后必须检查从插入点到根的路径，因为只有该路径上节点的子树高度可能变化，失衡节点必为路径上首个平衡因子绝对值为2的祖先；需自底向上更新高度、判断失衡并执行对应单旋（ll/rr）或双旋（lr/rl），且每次旋转后须重算相关节点高度并确保父指针正确赋值。

c++实现平衡二叉树avl的高度自平衡 _ 节点旋转逻辑代码【源码】

AVL树插入后为什么必须检查从插入点到根的路径

因为AVL树的平衡性只定义在每个节点的左右子树高度差 ≤ 1，而单次插入最多破坏这一性质于其祖先路径上。不沿路径回溯更新高度并判断是否失衡，就无法定位真正需要旋转的位置——失衡节点总是**最深的那个满足 |height(left) − height(right)| > 1 的祖先**。

常见错误是只检查父节点或仅在递归返回时无条件旋转，结果导致旋转后高度未重算、或对非失衡节点误操作，整棵树失去平衡甚至出现负高度。

每次递归插入返回前，必须用 updateHeight() 重算当前节点高度：node->height = 1 + max(height(node->left), height(node->right))
紧接着调用 getBalanceFactor()（即 height(left) - height(right)），仅当值为 2 或 -2 时才触发旋转
旋转后，参与旋转的节点（如 node 和 child）高度必须重新计算，且它们的父节点高度也需在上层递归中更新

四种旋转场景怎么对应 balance factor 和子树结构

旋转类型不由插入方向单独决定，而由失衡节点的 balanceFactor 和其**失衡子节点的 balanceFactor 共同决定。漏判子节点的因子会导致 LL/RR 错写成 LR/RL，树结构直接损坏。

假设当前失衡节点为 y，其左子为 x（即 balanceFactor(y) == 2）：

若 x->balanceFactor == 1 → LL 情况 → 执行 rotateRight(y)
若 x->balanceFactor == -1 → LR 情况 → 先 rotateLeft(x)，再 rotateRight(y)

同理，balanceFactor(y) == -2 时看右子 z：z->balanceFactor == -1 是 RR，为 1 则是 RL。注意：子节点的 balanceFactor 必须在旋转前读取，因为一次旋转会改变其值。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

rotateLeft / rotateRight 函数里最容易写错的三个指针操作

旋转本质是局部子树重构，核心是三处指针重连。写错任意一处就会断链、成环或指向空节点却未判空。

rotateRight(Node* y) 中：x 是 y->left，必须先保存 x->right（记为 T2），再令 y->left = T2 —— 若漏这步，x 原来的右子树就丢失
x->right = y 必须在 y->left = T2 之后，否则 y 的左子被覆盖前无法拿到 T2
旋转后要重新设置 y->height 和 x->height，顺序不能颠倒：必须先算 y->height（它依赖更新后的左右子），再算 x->height（它依赖新的 y）

示例关键段（右旋）：

Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;
    x->right = y;
    y->left = T2;  // 这行不能省，也不能和上一行互换
    y->height = 1 + max(height(y->left), height(y->right));
    x->height = 1 + max(height(x->left), height(x->right));
    return x;
}