计算AVL树的平衡因子

Question

大家好！

我不知道如何计算AVL树中节点的平衡因子。有人可以解释吗？

这是我发现的计算余额的代码：

size_t height() const
        {
            size_t left_h = (left == nullptr) ? 0 : left->height();
            size_t right_h = (right == nullptr) ? 0 : right->height();
            return left_h < right_h ? right_h + 1 : left_h + 1;
        }

        signed char balance()
        {
            size_t left_h = (left == nullptr) ? 0 : left->height();
            size_t right_h = (right == nullptr) ? 0 : right->height();
            return right_h - left_h;
        }

此外，这是带有已计数余额的AVL树的示例：

预先感谢！

Answer 1

作为维基百科states

在二叉树中，节点的平衡因子被定义为其两子树的高度差。

因此，为了计算节点的平衡，您必须计算其子节点的高度。

让我们分析计算余额的代码：

signed char balance()
{
    // calculate height of the children
    // check whether left is absent, if yes: 0, else calculate height on left 
    size_t left_h = (left == nullptr) ? 0 : left->height();
    // the same with right
    size_t right_h = (right == nullptr) ? 0 : right->height();

    // return the difference of heights of the right child and the left child
    return right_h - left_h;
}