Formule pour trouver nombre d'arbres possibles AVL avec des noeuds n

Question

laisser le nombre de nœuds soit 3.
Si a, b, c .. sont dans l'ordre c> a> b AVL alors possibles sont: n=1 gives 1,n=2 gives 2..(look image)

Comme nous le savons pour un BST, il est 2n C n/(n + 1).
Quelqu'un at-il essayé de déduire une formule qui peut trouver le nombre d'arbres avl lorsque le nombre de nœuds est donné. Exemple de question: quel est le nombre d'arbres avl possibles avec 11 nœuds?

Answer 1

Je doute que cette formule existe. Mais vous pouvez trouver nombre d'arbres possibles AVL avec programmation dynamique, remplissant le tableau 2D, où n est le nombre de noeuds, h est la hauteur des arbres, puis additionnez toutes non nulles entrées n-noeuds:

F(n, h) = Sum[by all possible i]{F(i,h-1)*F(n-1-i,h-1)} + 
      Sum[by all possible j]{F(j,h-1)*F(n-1-j,h-2)} + 
      Sum[by all possible k]{F(k,h-2)*F(n-1-k,h-1)} 

Explication: nous peut faire n-nœuds h-hauteur AVL arbre, reliant le nœud racine avec deux arbres valides de hauteur égale (h-1), ou avec (h-1) et (h-2) des arbres, ou avec (h-2) et (h-1) arbres.