Self Derivation

Question

I want to derive a formula that, with n nodes how many AVL trees can possible.

we know that, with 0 ==> 1,with 1 ==> 1, with 2 ==> 2, with 3 ==> 1

with 4 ===> root is fixed ==> remaining 3 nodes we have to distribute on left side and right side

LEFT	RIGHT	POSSIBLE
3	0	Can't possible
2	1	possible ==> N(2) * N(1) = 2*1 =2
1	2	possible ==> N(1) * N(2) = 1*2 =2
0	3	Can't possible

===> N(4) = 2+2 =4

with 5 ===> root is fixed ==> remaining 4 nodes we have to distribute on left side and right side

LEFT	RIGHT	POSSIBLE
4	0	Can't possible
3	1	possible ==> N(3) * N(1) = 1*1 =1
2	2	possible ==> N(2) * N(2) = 2*2 =4
1	3	possible ==> N(1) * N(3) = 1*1 =1
0	4	Can't possible

===> N(5) = 1+4+1 =6

 

with 6 ===> root is fixed ==> remaining 5 nodes we have to distribute on left side and right side

LEFT	RIGHT	POSSIBLE
5	0	Can't possible
4	1	Can't possible
3	2	possible ==> N(3) * N(2) = 1*2 =2
2	3	possible ==> N(2) * N(3) = 2*1 =2
1	4	Can't possible
0	5	Can't possible

===> N(6) = 2+2 =4

 

with 7 ===> root is fixed ==> remaining 6 nodes we have to distribute on left side and right side

LEFT	RIGHT	POSSIBLE
6	0	Can't possible
5	1	Can't possible
4	2	possible ==> N(4) * N(2) = 4*2 =8
3	3	possible ==> N(3) * N(3) = 1*1 =1
2	4	possible ==> N(2) * N(4) = 2*4 =8
1	5	Can't possible
0	6	Can't possible

===> N(7) = 8+1+8 =17

Can't possible cases we can easily find by maximum height achieve by left nodes, and right nodes atmost differ by 1.

Can we simplify further.... i am not able to do further...

Comments

how N(3)=1??

it should be 4

how 0=>1??

it will be 0

---

more over in such a way , u cannot say balance is maintained

---

Srestha I think you are confusing N(3) with the number of nodes required to make an avl tree of height 3.

Here N(3) is something different. It is the number of avl tree structures possible with 3 nodes.