AVL树插入后必须自底向上检查并旋转，因插入可能使某节点平衡因子变为±2；首次发现失衡节点即旋转修复，再向上递归检查。LL、RR、LR、RL四种旋转由插入路径方向决定，旋转需更新涉及节点高度并返回新根。
AVL树插入后为什么必须检查并可能旋转
因为AVL树要求任意节点的左右子树高度差（平衡因子）绝对值 ≤ 1。单纯插入可能导致某节点平衡因子变为 ±2，此时必须通过旋转恢复平衡。关键不是“插完再统一调整”，而是从插入点向上回溯到根，**首次发现失衡节点就立即旋转修复**，之后其父节点高度变化可能引发更高层失衡，需继续向上检查。
四种旋转场景怎么判断和选择
失衡节点记为 node，插入发生在它的子树中。旋转类型由插入路径的“方向组合”决定：
- LL：插入发生在
node->left->left—— 右旋node - RR：插入发生在
node->right->right—— 左旋node - LR：插入发生在
node->left->right—— 先对node->left左旋，再对node右旋 - RL：插入发生在
node->right->left—— 先对node->right右旋，再对node左旋
实际编码中，通常用平衡因子（height(node->right) - height(node->left)）和插入后子树高度变化方向联合判断，避免重复遍历。
旋转操作本身要改哪些指针
旋转本质是局部子树重构，只修改涉及的 3–4 个节点的 left/right 指针，不改变键值。以右旋为例（LL）：
立即学习“C++免费学习笔记（深入）”；
Node* rotateRight(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
// 更新高度（假设 height() 是成员函数或辅助函数）
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
注意：T2 非空时，它原属于 x 的右子树，旋转后成为 y 的左子树；所有旋转都必须更新参与节点的高度，否则后续平衡因子计算错误。
插入函数里如何嵌入平衡维护逻辑
标准递归插入返回新子树根，每层返回前检查当前节点是否失衡，并执行对应旋转。典型结构如下：
Node* insert(Node* node, int key) {
// 1. 标准BST插入
if (!node) return new Node(key
);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node; // 重复键，不插入
// 2. 更新当前节点高度
node->height = 1 + max(height(node->left), height(node->right));
// 3. 计算平衡因子
int bf = getBalanceFactor(node);
// 4. 四种失衡情况处理（返回旋转后的新根）
if (bf > 1 && key < node->left->key) // LL
return rotateRight(node);
if (bf < -1 && key > node->right->key) // RR
return rotateLeft(node);
if (bf > 1 && key > node->left->key) // LR
return rotateLeftRight(node);
if (bf < -1 && key < node->right->key) // RL
return rotateRightLeft(node);
return node; // 无需旋转，返回原节点}
容易忽略的点：旋转后必须返回新根（如 rotateRight 返回 x），否则父节点的指针会指向被“转下去”的旧根，导致树断裂；另外，getBalanceFactor 必须用 height(right) - height(left)，符号反了会导致 LL/RR 判断颠倒。
