C++实现简单的平衡二叉树平衡因子计算 _ 深度差逻辑【源码】

平衡因子是左子树高度减右子树高度的有符号差值，即 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)，反而破坏了调用栈的逻辑。