C++实现AVL树平衡旋转 _ 左右旋转逻辑代码实现【源码】

A VL树旋转必须返回新根节点，因二叉链表无父指针，调用方需用返回值重连子树；height函数对空节点须返回−1以保证平衡因子计算正确；四种失衡类型严格对应单旋或双旋，且判断条件中需包含等号。

实现A VL树的平衡旋转，可不是简单地“左右各写一个函数”就万事大吉了。真正的难点在于，旋转后必须同步更新节点高度、妥善处理父指针（如果采用三叉链结构），而且一次旋转往往不够——插入节点后，可能需要从插入点开始，沿着路径向上逐层检查平衡性，最多执行一次旋转才能恢复全局平衡。

为什么rotateLeft和rotateRight必须返回新根节点

这其实是由A VL树常见的实现方式决定的。大多数情况下，节点采用二叉链表结构，这意味着节点本身没有指向父节点的指针。那么问题来了：旋转操作会彻底改变局部子树的根节点，如果旋转函数不把新的根节点“告诉”上层调用者，上层代码该如何正确地重新建立链接呢？

举个例子就清楚了。假设因为右子树的插入导致了失衡，你调用了rotateLeft进行左旋。旋转完成后，原来那个失衡的节点已经不再是这棵子树的根了。如果旋转函数是void类型，调用方手里拿着的还是那个旧指针，原父节点的right字段就无法指向真正的新根，结果就是链表在此处“断裂”，整棵子树都丢失了。

这就是一个典型的陷阱。很多初学者会写出void rotateLeft(Node* node)这样的函数，内部虽然正确地调整了node->right和node->right->left的指向，但调用方却无法感知到这个变化，程序逻辑自然就错了。

正确的做法应该遵循以下三点：

• 函数签名设计为Node* rotateRight(Node* y)，传入失衡节点y，返回旋转后的新根节点（也就是原来的y->left）。
• 调用时必须用返回值进行重连，例如：x->right = rotateLeft(x->right)。
• 在旋转函数内部，所有指针关系重新建立后，必须立即调用updateHeight来更新所有涉及节点的高度，为后续的平衡检查做好准备。

getBalanceFactor的计算顺序与边界处理

平衡因子的定义很明确：左子树高度减去右子树高度。但魔鬼藏在细节里。很多实现会直接写成height(node->left) - height(node->right)，这看似没问题，实则暗藏一个关键前提：height函数对于空节点（nullptr）必须返回-1，而不是0。

为什么必须是-1？我们来看一个反例。如果height(nullptr)返回0，那么对于一个叶子节点（左右子树皆空），计算出的平衡因子将是 0 - 0 = 0，这看起来是对的。但等等，叶子节点自身的高度通常是0。按照这个逻辑，一个高度为0的节点，其左右子树“高度”也是0，这在概念上是矛盾的，也会导致某些边界情况下的计算错误。正确的逻辑是，空树的高度定义为-1，这样叶子节点的平衡因子才是 (-1) - (-1) = 0。

来看一段有问题的代码：

int height(Node* n) { return n ? n->height : 0; } // ❌ 这会导致叶子节点的 balance 被误算为 1

而正确的写法应该是：

int height(Node* n) { return n ? n->height : -1; } // ✅ 确保空节点高度为-1，计算逻辑自洽

因此，实现getBalanceFactor时必须严格遵循这个高度定义，并且绝对不能省略空指针判断。即使你确信某个节点非空，为了代码的健壮性和避免未定义行为，这个检查也必不可少。

四种失衡场景如何对应到旋转组合

A VL树的平衡调整不是乱猜的，它严格对应着四种失衡类型。判断的依据是当前节点的平衡因子，以及其较重一侧子节点的平衡因子。这里千万不能凭感觉，必须对号入座：

• LL型（左左）：当balance > 1且getBalanceFactor(node->left) >= 0时触发。这意味着新节点插入在左子树的左侧，只需一次右单旋即可。
• RR型（右右）：当balance < -1且getBalanceFactor(node->right) <= 0时触发。这意味着新节点插入在右子树的右侧，只需一次左单旋即可。
• LR型（左右）：当balance > 1且getBalanceFactor(node->left) < 0时触发。这意味着新节点插入在左子树的右侧，需要先对左孩子进行一次左旋（转化为LL型），再对当前节点进行一次右旋。
• RL型（右左）：当balance < -1且getBalanceFactor(node->right) > 0时触发。这意味着新节点插入在右子树的左侧，需要先对右孩子进行一次右旋（转化为RR型），再对当前节点进行一次左旋。

这里有一个极其关键的细节：判断条件中的等号（=）必须包含。为什么？考虑一种情况，插入操作可能使一个原本平衡（因子为0）的子树变成轻微失衡（因子为+1或-1），这种情形仍然属于LL或RR型，需要用单旋解决。如果漏掉了等号，这部分失衡情况就会被错误地忽略，导致树最终失去平衡。

插入后updateHeight和平衡检查的调用时机

这是另一个容易出错的地方。高度更新和平衡检查的顺序至关重要，必须遵循一个原则：高度更新必须在旋转操作完成之后、向上回溯检查之前进行。

一个典型的错误流程是：在递归插入函数返回后，立即更新当前节点的高度，然后紧接着检查平衡因子。问题在于，此时其子树可能已经失衡，但你用来计算平衡因子的“高度”却是更新前、未失衡状态下的旧值，这必然导致误判。

正确的递归插入流程应该是这样的：

• 向左右子树递归插入新节点。
• 递归返回后，立即更新当前节点的高度：height = 1 + max(height(left), height(right))。
• 基于刚更新的高度计算当前节点的平衡因子。
• 根据平衡因子及其子节点的平衡因子，判断属于四种失衡类型的哪一种，并执行相应的旋转（或不旋转）。
• 如果执行了旋转，旋转函数内部已经更新了所有相关节点（至少涉及三个节点）的高度。这里顺序很重要：必须先更新位置最低的“孙子”节点高度，然后更新“儿子”节点，最后更新新的根节点。顺序错了，中间计算的高度值就不准确。

最后再强调一遍最容易被忽略的一点：旋转操作本身就是一个改变结构的过程，必须在函数内部一鼓作气地完成所有节点高度的修正，不能留给外部流程，否则状态就会不一致。