平衡因子是左子树高度减右子树高度的有符号差值，即 bf = height(left) - height(right)，取值仅为 -1、0 或 1；空节点高度定义为 -1，以确保叶子节点高度为 0，且旋转后仅需更新 x、y 两个节点的高度和平衡因子。
平衡因子怎么算？别直接用 abs(left_height - right_height)
很多人一上来就想当然地认为平衡因子就是“左右子树高度差的绝对值”，但 A VL 树的定义里要求的是有符号差值——左子树高度减右子树高度，结果只能是 -1、0 或 1。如果写成 abs(...)，方向信息就丢了，后续判断哪边高、该做哪种旋转（LL / LR / RR / RL）时，逻辑会完全跑偏。
一个常见的错误现象是：insert 之后树看起来“没歪”，但插入新节点后却触发了错误的旋转，甚至破坏了 BST 性质——根本原因就是平衡因子的符号错了，导致旋转类型误判。
- 必须单独维护每个节点的
height字段（或每次递归计算），不能只靠bf反推 - 更新平衡因子必须在更新高度之后：先递归算出左右子树高度，再算当前
bf，最后更新当前节点height = max(left_height, right_height) + 1 - 若用递归求高度（不缓存），时间复杂度会退化成 O(n) 每次，务必避免在
getBalanceFactor()里重复调用两次getHeight()
getHeight() 必须处理空指针，且返回 -1 还是 0？
标准 A VL 实现中，空节点（nullptr）的高度定义为 -1，这样叶子节点的高度才是 0（两个子树都为空 → max(-1, -1) + 1 = 0）。这个约定直接决定了 bf 计算结果是否符合定义。
错误示例：如果把空节点高度设为 0，叶子节点高度就变成了 1，所有 bf 值整体偏移。插入单个节点后根节点 bf 就会是 1 而非 0，后续逻辑全乱。
- 统一用
getHeight(nullptr) → -1 - 对应地，
getNodeHeight(Node* n)应写成：int getNodeHeight(Node* n) { return n ? n->height : -1; } - 千万别在
getNodeHeight里对n做递归调用——那是updateHeight()的事
插入后只更新路径上节点的 height 和 bf，别全量重算
A VL 插入是自底向上修复的，只有从插入点到根的路径上的节点高度可能变化，其余子树不受影响。逐层回溯时，每层只需做三件事：
- 用左右子节点当前
height更新本节点height - 立即计算本节点新
bf = getNodeHeight(n->left) - getNodeHeight(n->right) - 若
bf超出 [-1,1]，才触发旋转；旋转后要重新设置参与旋转的 2~3 个节点的height和bf
性能关键点：没被访问的子树，其 height 字段保持原值，不碰；bf 不存储也行，但每次判断旋转前必须实时算——因为旋转会改变局部结构，缓存的 bf 很快过期。
旋转后哪些节点的 height 和 bf 必须重置？
以 rightRotate(y) 为例（y 是失衡节点，x 是 y 的左孩子）：旋转后，x 成为新子树根，y 变为其右孩子。此时只有 x 和 y 的 height 和 bf 可能变；x 的原右子树（即 y 的左子树）和 y 的右子树未参与结构调整，高度不变。
- 必须重算
x->height和y->height（顺序不能反：先 y 再 x，因为 x 的高度依赖 y 的新高度） - 接着重算
x->bf和y->bf—— 注意此时它们的子节点指针已更新，必须用新拓扑 - 其他节点（如 x 的左子树根、y 的右子树根）的
height和bf完全不用动
容易被忽略的是：旋转函数内部不负责更新祖父节点的指针或高度，那是插入函数回溯时的工作。很多初学者在 rightRotate 里强行改 parent->left/right 或调用 updateHeight(parent)，反而破坏了调用栈的逻辑。
