平衡因子实时计算需在节点中缓存height字段,插入/删除后自底向上回溯更新:每层用子节点height重算自身height=max(left→height, right→height)+1,并立即计算balance=left→height−right→height;空子树高度为-1。

平衡因子怎么实时算,别每次遍历整棵树
平衡因子本质是左右子树高度差,实时更新的关键在于「自底向上回溯时顺手算」。如果每次调用 getBalanceFactor 都递归求左右高度,时间复杂度直接退化到 O(n),完全失去 AVL 树的意义。
正确做法是在每个节点里缓存 height 字段,插入/删除后沿路径向上修正——从被修改的叶子一路回到根,每层用子节点的 height 重算自己的 height = max(left->height, right->height) + 1,同时立即算出 balance = left->height - right->height。
- 必须把
height存在节点结构体里,不能靠函数临时算 - 所有修改子树的操作(插入、删除)完成后,必须做一次自底向上的高度/平衡因子更新,不能只改局部
- 注意空指针:叶子节点的子节点为
nullptr,对应高度按 -1 处理(这样单节点高度才是 0)
四种旋转怎么选,看的是失衡节点和插入路径的组合
不是「左子树高就右旋,右子树高就左旋」这么简单。AVL 的四种旋转由「失衡节点的平衡因子」和「导致失衡的那个子节点的平衡因子」共同决定,本质是看插入发生在「内侧」还是「外侧」。
假设当前失衡节点为 node,它左子树过高(node->balance == 2):
立即学习“C++免费学习笔记(深入)”;
- 如果
node->left->balance == 1:插入发生在左子树的左侧 → 执行rotateRight(node)(LL 型) - 如果
node->left->balance == -1:插入发生在左子树的右侧 → 先rotateLeft(node->left),再rotateRight(node)(LR 型)
同理,右子树过高(node->balance == -2)时:node->right->balance == -1 是 RR,== 1 是 RL。关键点是必须检查子节点的 balance 值,而不是猜方向。
旋转后哪些节点的 height 和 balance 必须重算
旋转只是指针交换,不自动更新高度和平衡因子。只重算参与旋转的 2~3 个节点就够了,其余不受影响。
- 单旋(LL/RR):只涉及
node和它的左/右孩子,重算这两个节点的height和balance - 双旋(LR/RL):涉及
node、node->left(或right)、以及更下一层的孙子节点,共三个节点需重算 - 千万别在旋转函数里递归更新整棵子树高度——这是常见性能陷阱
示例:LL 旋转后,原 node->left 成了新根,它的新高度取决于自己左右子树;原 node 现在是右孩子,它的新高度只取决于自己新的左右子树(其中一边刚被换掉)。
删除操作比插入更容易破坏平衡,回溯时得检查每一层
插入最多引发一次失衡(因为只增加一层),但删除可能让某条路径变短,导致从删除点到根的路径上多个节点都出现 balance 超出 [-1,1] 范围。所以删除后的修复必须「一路回溯到根」,对每个祖先节点都检查 balance 并必要时旋转。
- 不能删完只修一次——哪怕某层旋转后暂时平衡了,上层仍可能失衡
- 旋转后子树高度可能变化,必须更新该层节点的
height,否则上层计算会错 - 特别注意:某次旋转可能让原本平衡的上层节点变得不平衡(比如 RL 旋转后,原祖父节点高度减 1),所以回溯不能中途停止
真正麻烦的不是旋转逻辑本身,而是忘记在回溯路径上持续更新 height——一个没更新,后面全错。


















