c++ - 从其子节点的余额计算 AVL 树节点余额

Question

假设我有一个 AVL 树，它的节点将自己的平衡因子存储为单个整数。

如果我知道它的左右子节点的平衡因子，我如何计算节点 N 的平衡因子。

请注意，我没有rHeight 和 lHeight，所以bal(N) = lHeight - rHeight不是一个选项。

Answer 1

简短的回答 - 你不能。

长答案：

考虑这两棵树：

           A
        /     \
     B           C                   A
   /   \       /   \                / \
  D     E     F     G              B   C
 / \   / \   / \   / \
H   I J   K L   M N   O

它们具有相同的平衡因子，但它们的高度不同。

所以，如果你只有孩子的平衡因子，你不知道那个子树有多高，因此你不能只用它来计算父母的平衡因子。