非递归AVL旋转必须显式维护父指针或栈以回溯路径，否则无法更新父节点子指针；插入最多一次失衡，删除可能多层失衡且需处理中序后继；旋转函数宜用Node**传参以直接修改父节点子指针。
为什么非递归AVL旋转必须维护父指针或栈
递归实现靠函数调用栈隐式记录路径，而非递归必须显式保存从根到插入/删除节点的完整路径。否则无法向上回溯做平衡调整——rotateLeft、rotateRight操作后，父节点的子指针根本不知道要更新成谁。
常见错误是只用一个current指针遍历到底，结果发现失衡节点后，既找不到它的父节点，也搞不清自己是从左子树还是右子树上来的。这时候要么加父指针（每个节点存parent），要么用std::stack存访问路径（推荐）。
- 加
parent字段：修改节点结构，所有插入/删除逻辑都要同步更新parent，容易漏写导致指针野指针 - 用
std::stack<Node*>：遍历时把每层节点压栈，回溯时逐个弹出，天然带方向信息（栈顶是当前节点，次顶是父节点） - 注意：栈里存的是
Node*，不是Node**；更新父节点子指针时需判断它是左孩子还是右孩子——靠比较地址：parent->left == current
非递归插入后如何从底向上检查并旋转
插入完成后，从栈中逐个弹出节点，重新计算每个节点的height（高度 = max(left→height, right→height) + 1），再算平衡因子bf = left→height - right→height。一旦发现bf < -1 || bf > 1，立即停止向上，就地做旋转。
关键点在于：旋转后，该子树根变了，必须把新根“接回”原父节点。而你手里只有父节点指针和方向信息，所以得用双重指针技巧或显式分支判断：
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
if (parent->left == oldRoot) {
parent->left = newRoot;
} else {
parent->right = newRoot;
}- LL型（左左）：插入在左子树的左子树 → 单右旋
rotateRight(parent) - RR型（右右）：插入在右子树的右子树 → 单左旋
rotateLeft(parent) - LR型（左右）：先对左孩子左旋，再对当前节点右旋
- RL型（右左）：先对右孩子右旋，再对当前节点左旋
- 旋转后，只更新参与旋转的 3 个节点高度（不是整条路径），然后跳出循环——更高层节点高度可能已变，但平衡性不会恶化（AVL性质保证）
delete操作比insert更麻烦在哪
insert最多引发一次失衡，而delete可能造成多层连续失衡，必须一路检查到根。更麻烦的是：被删节点若有两个子节点，需用中序后继（或前驱）替换，这个后继本身可能带子树，替换后它原来的位置也要做平衡——相当于又触发一次delete。
非递归实现时，这意味你要在栈里存两套路径：一套是查找待删节点的路径，另一套是查找其中序后继的路径（如果需要）。实际做法是统一处理：找到待删节点后，把它和后继之间的所有中间节点都压入同一个栈，确保回溯时能覆盖全部受影响区域。
- 别直接
delete节点内存，先摘下来，再调用rotate，最后delete——避免旋转过程中访问已释放内存 - 后继节点一定没有左子树（定义决定），但它可能有右子树，这个右子树要接到后继原位置上，然后再对那个位置做平衡
- 高度更新不能跳过：哪怕某层没旋转，只要子树高度变了，当前节点
height就得重算，否则上层bf计算错误
rotateLeft/rotateRight函数怎么写才适配非递归场景
非递归旋转函数不能依赖隐式上下文，输入必须包含明确的“被旋节点”和“其父节点”（或父节点的子指针地址）。最稳妥的是传入Node** rootPtr——即父节点对应子指针的地址，这样旋转后直接改*rootPtr就行，不用再判断左右。
例如rotateLeft(Node** rootPtr)内部：先取Node* oldRoot = *rootPtr，再取Node* newRoot = oldRoot->right，做完指针交换后，写*rootPtr = newRoot。调用时传&(parent->left)或&(parent->right)，完全规避方向判断。
- 传
Node**比传Node*&更清晰，C++里也更常见于系统级代码 - 旋转函数内部不更新
height，那是调用方的责任——因为高度更新时机取决于你是insert还是delete回溯路径 - 务必检查
newRoot是否为空，尤其delete场景下，后继可能没有右子树，rotateRight时oldRoot->left可能为nullptr
真正难的不是旋转本身，而是路径管理与高度传播的耦合。稍不注意，栈里少压一层、高度漏更新一次、父指针没改对，整棵树就 silently 不平衡了。
