AVL arbres minimum nœud

Quel est le nombre minimum de nœuds dans un arbre AVL de hauteur h? J'ai fait quelques recherche sur Internet, mais ils sont tous tellement confus.

InformationsquelleAutor Chin | 2012-10-20
  1. 9

    n(h) être le nombre minimum de nœuds d'un arbre AVL de hauteur h, alors:

    n(0)=1, n(1)=2
n(h)= 1+n(h-1)+n(h-2)
    InformationsquelleAutor beNick
  2. 3

    le nombre minimum de nœuds dans un arbre AVL pour un arbre de hauteur h. L'équation suivante doit démontrer l'appel récursif de la N(h) de la fonction.

    formula N(h)=1+N(h-1)+N(h-2)

    Puisque nous savons que N(0)=1 ,N(1) = 2, N(2) = 4,
    par exemple: nous pouvons réduire l'équation suivante pour ces personnes connues pour h = 6.

    N(3)=1+N(3-1)+N(3-2)=1+N(2)+N(1)=7

N(4)=1+N(4-1)+N(4-2)=1+N(3)+N(2)=12

N(5)=1+N(5-1)+N(5-2)=1+N(4)+N(3)=20

N(6)=1+N(6-1)+N(6-2)=1+N(5)+N(4)=33
    InformationsquelleAutor Rana Priyanka
  3. 0

    Un arbre AVL de hauteur h a au moins 2(h/2)-1 nœuds internes.

    Preuve: soit n(h) est le nombre minimal de nœuds internes dans un arbre AVL de hauteur h.

    n(1)=1 et n(2)=2. Ainsi, le lemme est titulaire pour h=1 et h=2.

    InformationsquelleAutor NullPoiиteя