CODEWITHSUNDEEP
c++algorithmdata-structuresavl-tree
NixoN
NixoN

Reputation: 683

Counting the balance factor for AVL trees

Hello everyone!

I can't get the idea of how we count a balance factor for nodes in AVL tree. Can somebody explain it?

Here's the code of counting the balance, that I found:

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

Also, here is the example of AVL tree with counted balances:

Balances of a Nodes

Thanks in advance!

Upvotes: 0

Views: 1414

Answers (1)

khurshid juraev
khurshid juraev

Reputation: 36

As Wikipedia states

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

So, in order to calculate the balance of a node, you have to calculate the heights of its children.

Let's analyze the code which calculates balance:

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

Upvotes: 2

Related Questions