Minimal AVL Tree Recurrence
Let denote the smallest size of an AVL tree of depth . Clearly and
Which of the following recurrences does satisfy?
- None of the above
The answer is 2.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The answer is T ( d ) = T ( d − 1 ) + T ( d − 2 ) + 1 .
In an AVL tree, each vertex has the property that the depths of its left and right subtrees differ by at most 1. In particular this is true of the root. Let us consider the subtrees of the root. One of them must have depth d − 1 , since the depth of the whole tree is d . The AVL property allows the other tree to have depth d − 1 or d − 2 (it can't be d since that is the depth of the entire tree). The minimality of the size of the tree implies that in fact the depth of the second subtree must be d − 2 . Furthermore, Since the entire tree is of minimal size, the subtrees themselves must be of minimal size for their depths, so that their sizes are T ( d − 1 ) and T ( d − 2 ) respectively. Adding 1 for the root gives the relevant recurrence.