计算 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

In a binary tree, the balance factor of a node is defined to be the height difference of its two-child sub-trees.

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

我们来分析一下计算余额的代码：

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;
}

计算 AVL 树的平衡因子

Counting the balance factor for AVL trees

c++

algorithm

data-structures

avl-tree