0
$\begingroup$

Find a function that bounds from above and below (asymptotic) the rank of the root r in an AVL tree,
i.e. find a function $f(n)$ so there exists a constant $c>0$ that for every AVL tree with $n$ nodes so $c * f(n)\le rank(r)\le n-c*f(n) $.

$rank(r)$ gets his maximum value when his sub-left tree contains maximal number of nodes and because it's an AVL tree, for tree with height $h$ the sub left tree will be with height of $h-1$ and the number of nodes will be maximal when the sub tree is a full tree with $2^{h-2}-1$ nodes hence we get:
$rank(r)\leq 2^{h-2}-1+1=2^{h-2}$

On the other hand, $rank(r)$ gets his minimal value when his sub left tree contains a minimal number of nodes and it happens when the sub left tree is a fibonacci tree with height of $h-2$, therefore
$rank(r) \geq \phi ^{h-2}+1$.

Now I need to find f as a function of the number of nodes $n$ and not the height $h$. Am I in the right direction?
Would apricciate any help how to continue, Thanks.

$\endgroup$
0
$\begingroup$

First of all, it's not $2^{h-2}$, it's $2^h$.

The number of nodes $n$ in a full binary tree, is at most $n=2^{h+1}-1$, where $h$ is the height of the tree. A tree consisting of only a root node has a height of 0.how to calculate h:

Straight outta wiki https://en.wikipedia.org/wiki/AVL_tree

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You are completely right! Don't know why I missed that, Thanks:) $\endgroup$ – Emma Apr 15 at 6:51

Your Answer

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

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