0
$\begingroup$

Looking at the tree on the left it seems that the triangles represent leaves of the avl tree. To arrive at the balancing of -2 besides the node y the right subtree must have 2 nodes while the left subtree has a maximum of 4 nodes. Thus 2-4 = -2. However what does the h indicate?

avl tree

$\endgroup$
1
  • 1
    $\begingroup$ The triangles are usually used to represent subtrees. And the $h$ is the height of the subtree. The integer beside a node is the height differences of its subtrees. $\endgroup$
    – Russel
    Oct 26, 2022 at 13:49

1 Answer 1

1
$\begingroup$

It is probably the height of the subtrees, i.e. the length of a longest path from the root to a leaf. Doing the balancing leaves us with a tree of height $h+2$ where we started with height $h+3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.