0
$\begingroup$

I studying the related question.

https://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node

but it's not so general.

In-fact, We want to know with N keys, how many different AVL Tree, we can make?

we know with N=1 key is 1 AVL Tree. with N=2 key we have 2 different AVL Tree, but in general we can make any recurrence formula? for example for N=4, N=5 and so on.

$\endgroup$
  • $\begingroup$ What have you tried on your own? Did you try working out the number for $n=1,2,3,4,5,6$ and looking for a pattern? Have you tried to derive a recurrence formula? Where did you get stuck? We want to help you, but without knowing what you tried and where you got stuck, we can't help you. Also, we expect you to make a serious effort before asking. While I'm asking: when do you count two AVL trees as "different"? And, in what context did you run into this question? $\endgroup$ – D.W. May 23 '14 at 21:33
  • $\begingroup$ I'm Sorry for my lack of knowledge !! i want to know with N key, how many different AVL can be constructed? I couldn't find a pattern up to yed :(. Would U Please Help Me ! $\endgroup$ – user3661613 May 23 '14 at 21:43
  • $\begingroup$ @user3661613 What do you know about easier tree enumerations? Do you know how many different binary trees with $n$ nodes there are (Hint: Catalan-Number)? Do you know how many different Binary Search trees of size $n$ there are? $\endgroup$ – john_leo May 24 '14 at 9:30
5
$\begingroup$

Let $a_{n,h}$ denote the number of AVL trees with $n$ nodes and height $h$. It is straightforward to get a recurrence for $a_{n,h}$:

$$a_{n,h} = \sum_{k=1}^n \bigl(a_{k-1,h-1}a_{n-k,h-1} + a_{k-1,h-1}a_{n-k,h-2} + a_{k-1,h-2}a_{n-k,h-1}\bigr),~ n\geq h > 1,$$

with the initial conditions $a_{n,h} = 0$, if $h>n$ or $h\in\{0,1\}, n\neq h$, and $a_{0,0} = a_{1,1} = 1$.

The numbers you are looking for then are $a_n = \sum_h a_{n,h}$.

Unfortunately there apparently is no known closed form for this sequence. The OEIS has a list of the first 1000 terms and maple + mathematica code to compute further ones (via the recursion).

$\endgroup$
  • $\begingroup$ can u add any example to your explanation? it's more sophisticated if any example would be. $\endgroup$ – user3661613 May 24 '14 at 16:02

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.