<p>平衡因子应通过缓存高度在O(1)内计算：BF = get_height(node->left) - get_height(node->right)，其中get_height空节点返回0，非空返回node->height；旋转由当前节点与子节点BF组合触发（如LL型为BF=+2且左孩子BF=+1），仅需更新旋转涉及的三个节点高度；插入后须递归回溯更新高度并就地旋转。</p>
平衡因子怎么算？别直接用 height(left) - height(right)
平衡因子（Balance Factor）定义是左子树高度减右子树高度，但很多人写成 height(node->left) - height(node->right) 后发现性能爆炸——因为每次调用 height() 都要递归遍历整棵子树。BST 插入/删除频繁时，这会让单次操作从 O(log n) 退化到 O(n)。
真正可行的做法是在节点结构里缓存高度：int height，并在每次插入、删除后自底向上更新。更新逻辑很简单：
node->height = 1 + max(get_height(node->left), get_height(node->right))-
get_height(node)就是空节点返回 0，否则返回node->height
get_height(node->left) - get_height(node->right)。四种旋转怎么触发？看平衡因子组合，不是看哪边高
AVL 旋转只由当前节点及其子节点的平衡因子共同决定，不是“左边高就右旋”。比如：
- LL 型：当前节点 BF = +2，且左孩子 BF = +1 → 右旋
- LR 型：当前节点 BF = +2，但左孩子 BF = -1 → 先对左孩子左旋，再对当前节点右旋
- RR 型：当前节点 BF = -2，右孩子 BF = -1 → 左旋
- RL 型：当前节点 BF = -2，右孩子 BF = +1 → 先对右孩子右旋，再对当前节点左旋
旋转后哪些节点的高度要重算？只重算参与旋转的三个节点
以右旋为例（节点 y 是 x 的左孩子）：旋转只改变 x、y 和 y->right 这三个节点的父子关系，所以只有它们的 height 需要重新计算：
void rotate_right(Node*& x) {
Node* y = x->left;
x->left = y->right;
y->right = x;
// 只更新 y、x、x->left（即原 y->right）的高度
update_height(x);
update_height(y);
x = y; // 更新根指针
}update_height() 就是上面说的那行 1 + max(...)。如果顺手把整棵树都遍历一遍更新高度，纯属浪费。
insert 后怎么回溯调整？递归返回时检查并旋转，不是插完再遍历
AVL 插入必须用递归写法（或手动栈模拟），因为在插入路径上每个祖先节点都可能失衡。常见错误是插完再从根往下查 BF —— 这没法保证只旋转一次就平衡，还可能漏掉深层失衡。
立即学习“C++免费学习笔记（深入）”；
正确做法：插入函数返回新子树根，并在每一层返回前做两件事：
- 更新当前节点
height - 检查 BF，若绝对值 > 1，则旋转并返回新根
实际写的时候，最容易被忽略的是：旋转后必须确保父节点的指针指向新根（比如用 Node*& 引用传参），以及所有涉及高度的地方都调用 get_height() 而不是裸访问 node->height —— 因为 nullptr 时要返回 0，直接访问会段错误。
