J'ai besoin d'une formule générale pour calculer la hauteur minimale de l'arbre binaire et la hauteur maximale de l'arbre binaire. (pas l'arbre de recherche binaire)
9 Réponses :
Pensez à la manière dont la structure de l'arbre peut changer.
Par exemple, si l'arbre est complètement déséquilibré, c'est le pire des cas - chaque nœud aura exactement un enfant. Dans le meilleur des cas, l'arbre est terminé équilibré et chaque nœud a deux enfants.
Comme cela ressemble à des devoirs, je vais y laisser là-bas.
La hauteur maximale est N et la hauteur minimale (c'est-à-dire un arbre binaire parfait) est la (BOG BASE 2 (N + 1)) - 1
La hauteur min est de la formule N = 2 ^ (H + 1) -1 simplement résoudre pour h.
Si vous avez n éléments, la hauteur minimale d'un arbre binaire sera log2 (n) +1.
Pour un arbre binaire complet, la hauteur maximale sera N / 2.
Pour un arbre binaire non complet, la hauteur maximale sera n.
Comment savez-vous si l'arbre est plein ou non complet? Je suis conscient que la hauteur minimale est considérée comme un arbre équilibré.
Comme un arbre binaire complet ne pouvait contenir qu'un nombre impair de nœuds, la formule de la hauteur maximale de l'arbre serait (N + 1) / 2.
Tout d'abord, il peut y avoir une certaine différence sur la calcule la science informatique La hauteur d'un arbre, par rapport à la hauteur de la hauteur est déterminée dans des mathématiques discrètes (Théorie des graphes), cela peut être dû à l'existence de données à n'importe quel noeud (ou vertige), tandis que dans les mathématiques, c'est une approche théorique pure.
Donc, peut-être de son mieux, vous clarifiez lequel vous avez besoin.
Dans les mathématiques discrètes, les arbres sont classés comme des arbres m-ary, donc un Bin-Ary Tree est un arbre de 2 ary. Aussi à une hauteur donnée, il peut y avoir au plus 2 ^ h = l (feuilles). Cela est important de noter que cela confirme que La racine est en hauteur zéro, donc 2 ^ 0 = 1 feuille ... 1 vertice ... la racine.
donc donné n sommets, la hauteur d'un arbre est donnée par la formule n = 2 ^ (h + 1) - 1
Depuis que vous recherchez H, vous devez prendre le log2 des deux côtés de la formule n = 2 ^ (H + 1) - 1
Pour un arbre binaire complet, la hauteur maximale est log2 (n + 1) = log2 (2 ^ (H + 1)) Ce plafond est égal (log2 (n + 1) - 1) = h
Pour un arbre binaire non complet, la hauteur maximale = (n-1) Par conséquent, si vous avez des sommets, la racine doit être soustraite pour obtenir la hauteur maximale, en raison de la formule précédente ci-dessus (2 ^ h = l)
Pour les hauteurs min, extrapoler des règles ci-dessus.
La hauteur minimale est H = plafond (journal (n + 1) / journal (2) -1) Pour tout arbre binaire.
Si une racine peut avoir un nombre de feuilles jusqu'à 2 (0,1,2), alors:
Pour obtenir une hauteur minimale, chaque racine doit avoir autant de branches que possible. Dans ce cas, vous remarquerez que pour n = 1, hauteur = 0; pour n = 2 à n = 3, hauteur = 1; pour n = 4 à n = 7, hauteur = 2; pour n = 8 à n = 15, hauteur = 3 etc.
Vous pouvez donc remarquer que, pour chaque N, il existe un P tel que:
2 ^ p <= n <2 ^ (p + 1) et p = hauteur, donc hauteur = [log2 (n)]
n - Nombre de nœuds.
H - Hauteur de l'arbre binaire.
Arbre binaire complet: Ainsi, résolvant cette inégalité; Nous obtenons: Nous obtenons enfin: (LG: la base de journal 2) < p> Nous obtenons une hauteur minimale lorsque l'arbre binaire est terminé.
Ensuite, avec H Height N, il allait entre:
avec avec n-nœud nœuds La hauteur maximale possible est plancher (journal (n)) = CEIL (N + 1)) - 1 .
N-NODES La hauteur minimale possible est n-1 .
donné n nœuds:
Hauteur min: plancher (log2 (n))
Disons que vous avez 3 nœuds: plancher (log2 (3)) sera plancher (1,58) == 1 Sera le sol (log2 (4)) sera le sol (2) == 2 racine- > gaucher1-> gauche2
Ici, 3 nœuds donnent une hauteur de 2.
Vous allez avoir besoin d'être plus précis.