Trouver le minimum et le maximum de la hauteur dans un arbre AVL, étant donné un nombre de nœuds?

La solution ci-dessous est approprié pour régler les choses en main et d'acquérir une intuition, veuillez voir les formules exactes au bas de cette réponse pour les arbres de grande taille (54+ nœuds).

Bien la hauteur minimale est facile, il suffit de remplir chaque niveau de l'arbre avec des nœuds jusqu'à ce que de vous lancer. Cette hauteur est le minimum.

Pour trouver le maximum, de faire la même chose que pour le minimum, mais ensuite, retourner à l'étape précédente (supprimer le dernier placé nœud) et de voir si l'ajout de ce nœud à l'opposé de la sous-arbre (à partir de l'endroit où il était) viole l'AVL arbres de la propriété. Si elle le fait, votre hauteur max est juste votre hauteur min. Sinon cette nouvelle hauteur (qui devrait être à hauteur min+1) est votre hauteur max.

Si vous avez besoin d'un aperçu de ce que les propriétés d'un arbre AVL sont, ou une explication d'un arbre AVL, Wikipedia est un excellent endroit pour commencer.

Exemple:

Prenons le 7 exemple de nœud cas. Vous remplissez tous les niveaux et de trouver un complètement rempli arbre de hauteur de 3. (1 au niveau 1, 2 au niveau 2, 4 au niveau 3. 1+2+4=7 nœuds.) Cela signifie que 3 est votre minimum.

Maintenant trouver le max. Supprimer le dernier nœud et de les placer sur le sous-arbre gauche au lieu de droite. Le sous-arbre droit encore a la hauteur 3, mais le sous-arbre gauche maintenant a la hauteur 4. Cependant, ces valeurs diffèrent de moins de 2, de sorte qu'il est encore un arbre AVL. Par conséquent, votre hauteur max est de 4. (Qui est-min+1)

Tous les trois exemples travaillé ci-dessous (notez que les numéros correspondent à l'ordre de placement, PAS la valeur de):

---

Formules¹:

La technique décrite ci-dessus ne tient pas si vous avez un arbre avec un très grand nombre de nœuds. Dans ce cas, on peut utiliser les formules suivantes pour calculer exactement min/max.

Donné n nœuds²:

Minimum: ceil(log₂(n+1))

Maximum: étage(1.44*log₂(n+2)-.328)

Si vous êtes curieux, la première fois max-min>1 lorsque n=54.

¹Merci pour Jamie S pour amener cet échec le plus grand nœud de compte à mon attention.

²Ces formules sont de la Wikipédia AVL page, avec des constantes branché. La source d'origine est de Tri et de recherche par Donald E. Knuth (2e Édition).

OriginalL'auteur River

Permet de supposer que le nombre de nœuds est n

Essayer de trouver le minimum de la hauteur d'un arbre AVL serait la même chose que d'essayer de faire l'arbre complet c'est à dire remplir tous les nœuds à chaque niveau et ensuite passer au niveau suivant.

Donc, à chaque niveau le nombre de nœuds augmente par 2^(h-1) où h est la hauteur de l'arbre.

Donc à h=1, les nœuds(1) = 2^(1-1) = 1 nœud

pour h=2, les nœuds(2) = nœuds(1)+2^(2-1) = 3 les nœuds

pour h=3, les nœuds(3) = nœuds(2)+2^(3-1) = 7 les nœuds

donc il suffit de trouver le plus petit h, pour lequel les nœuds(h) est plus grand que le nombre de nœuds n.

Maintenant pour le problème de la hauteur maximale d'un arbre AVL:-

permet de supposer que l'AVL est un arbre de hauteur h, F(h) étant le nombre de nœuds dans l'arbre AVL,

pour sa hauteur maximale permet de supposer que son sous-arbre gauche FL et à droite de la sous-arborescence FR ont une différence de hauteur de 1(qu'il répond à l'AVL propriété).

Maintenant, en supposant que FL est un arbre de hauteur h-1 et FR un arbre de hauteur h-2.

maintenant le nombre de nœuds dans

F(h)=F(h-1)+F(h-2)+1 (Eq 1)

L'ajout de 1 sur les deux côtés :

F(h)+1=F(h-1)+1)+ F(h-2)+1) (Eq 2)

Nous avons donc réduit la hauteur maximale problème à un Fibonacci sequence. Et ces arbres F(h) sont appelés Les Arbres De Fibonacci.

Donc, F(1)=1 et F(2)=2

afin d'obtenir le maximum de hauteur il suffit de trouver l'indice de la le nombre de la suite de fibonacci qui est inférieur ou égal à n.

Donc l'application (Eq 1)

F(3)= F(2) + F(1)+ 1=4, donc si n est compris entre 2 et 4 de l'arbre aura hauteur 3.

F(4)= F(3)+ F(2)+ 1 = 7, même si n est compris entre 4 et 7 de l'arbre aura hauteur 4.

et ainsi de suite.

OriginalL'auteur Naman Choradia