高度与平衡因子

节点高度如何定义与计算？

• 高度: 该节点到最远叶节点经过的边数;
• 基准: 叶节点高度为 0, 空节点约定为 -1;
• 递推: height(node) = max(height(left), height(right)) + 1;

const getHeight = (node) =>
  node == null ? -1 : Math.max(getHeight(node.left), getHeight(node.right)) + 1;

• 代价: 每次递归求高度都是 O(n); 若在节点上缓存高度字段, 读取退化为 O(1), 这是 AVL 节点的常规做法;

平衡因子如何定义？

• 定义: 左子树高度 - 右子树高度;
• 空节点: 平衡因子为 0;
• 合法范围: AVL 树中每个节点的平衡因子只能是 -1、0、1;

const balanceFactor = (node) => (node == null ? 0 : getHeight(node.left) - getHeight(node.right));

为什么高度差要限制在 1 以内？

• 目的: 把树高约束在 O(log n), 使查找、插入、删除都保持 O(log n);
• 失衡: 平衡因子绝对值大于 1 的节点称为失衡节点, 必须通过旋转修复;
• 修复方式见 四种旋转;