je suis en train de lire Le manuel de conception d'algorithmes. L'auteur affirme que la hauteur d'un arbre est:
h = log n,
where
h is height
n = number of leaf nodes
log is log to base d, where d is the maximum number of children allowed per node.
Il ajoute ensuite que la hauteur d'un arbre de recherche binaire parfaitement équilibré serait:
h = log n
je me demande si n dans cette seconde déclaration, on entend "nombre total de nœuds feuilles"ou" nombre total de noeuds".
Ce qui soulève une question plus importante: existe-t-il une relation mathématique entre le nombre total de nœuds et la hauteur d'un arbre de recherche binaire parfaitement équilibré?
Réponses:
5 pour la réponse № 1sûr, n = 2^h où h, n dénotent la hauteur de l'arbre et le nombre de ses nœuds, respectivement.
croquis de preuve:
un arbre binaire parfaitement équilibré a
- un facteur de branchement réel de 2 à chaque nœud interne.
- longueurs égales du chemin racine pour chaque noeud feuille.
sur les nœuds feuilles dans un arbre binaire parfaitement équilibré:
comme le nombre de feuilles est le nombre de nœudsmoins le nombre de nœuds dans un arbre binaire parfaitement équilibré avec une hauteur décrémentée de un, le nombre de feuilles est égal à la moitié du nombre total de nœuds (pour être précis, la moitié n+1).
alors h varie seulement de 1, ce qui ne fait généralement pas dedifférence réelle dans les considérations de complexité. Cette affirmation peut être illustrée en se rappelant qu’elle revient aux mêmes variations que la définition de la hauteur d’un arbre à un seul noeud comme étant 0 (standard) ou 1 (inhabituel, mais peut être utile pour le distinguer d’un arbre vide).
2 pour la réponse № 2
Peu importe si vous parlez de tous les nœudsou simplement des nœuds feuilles: l'un ou l'autre est lié par le haut et le bas par l'autre multiplié par un facteur constant. Dans un arbre binaire parfaitement équilibré, le nombre de nœuds sur un niveau complet est le nombre de tous les nœuds des niveaux supérieurs à un.
0 pour la réponse № 3
Dans un arbre binaire complet, le nombre de nœuds (n) et la hauteur de l'arbre (h) ont une relation comme celle-ci ci-dessous.
n = 2 ^ (h + 1) -1
c'est tous les nœuds de l'arbre