I have some confusion with regards to AVL trees and the heights of various subtrees.

When initially reading the overview of the algorithms purpose(to keep the tree balanced) I thought it put limits on the maximum height difference between the shortest path and the longest path in the tree - my initial understanding is that they could only have a difference of 1.

But after re-reading this no longer appears to be the case? The description given on Wikipedia is the difference between the height of the left and right trees must only be a difference of 1 but this allows for subtrees with shorter paths.

What's going on?

  • $\begingroup$ The heigh of a node is the maximum level among its branches, this can cause what you noticed. The definition don't consider the lowest level sub-trees. $\endgroup$ – kelalaka Sep 15 '19 at 8:25
  • $\begingroup$ When initially reading the overview of the [algorithm's] purpose Which overview, where? Please cite (block-quote) and, if possible, hyperlink. $\endgroup$ – greybeard Sep 15 '19 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.