Nous sommes tombés sur une question dans Ici, je suis confus par cette question selon laquelle il y aura à la plupart des nœuds Par exemple, considérez ce problème:
dans le problème ci-dessus à la hauteur 2 Il y a 2 nœuds. Mais si nous calculons par formule: Il ne satisfait pas Thomas H. Cormen questions. veuillez me corriger si Je me trompe ici. Merci d'avance 
10 Réponses :
On dirait que votre formule dit qu'il y a au plus [n / 2 ^ h + 1] nœuds de hauteur h. Dans votre exemple, il existe deux nœuds de hauteur 2, ce qui est inférieur à votre maximum calculé de 4 (ISH).
Tout en calculant la liaison serrée pour
Dans ce cas, nous appelons l'assistant max-tassify qui prend o (h ) où H est la hauteur du sous-arbre enraciné sur le nœud actuel (pas la hauteur de la hauteur de nœud lui-même par rapport à l'arbre complet).
Par conséquent, si nous considérons le sous-arbre enraciné au nœud de feuille, il aura une hauteur 0 et un nombre de nœuds dans l'arborescence à ce niveau serait au plus N / 2 0 +1 = n / 2 (c.-à-d. h = 0 pour le sous-arbre formé à partir de nœud aux feuilles).
De même pour le sous-arbre enraciné à la racine réelle, la hauteur de l'arborescence serait journal (n) et dans ce cas, le nombre de nœuds à ce niveau serait de 1 étage de n / 2 logn +1 = [N / N + 1].
formule pour donc lorsque mais Il existe donc 2 nœuds que vous pouvez voir à partir de la figure. h est 2 et n = 10
Bien que cela soit mentionné dans CORLEN, la hauteur d'un nœud est la plus grande distance parcourue du nœud en feuille (le nombre d'arêtes), si vous prenez la hauteur pour être la distance d'un nœud de la feuille, c'est-à-dire à la feuille de la hauteur. est zéro et à racine la hauteur est log (n). La formule est correcte.
comme pour les feuilles que vous avez H = 0; Par conséquent, par la formule N / (2 ^ (H + 1))) h = 0; Le nombre maximum de feuilles dans le tas sera n / 2.
Qu'en est-il de la hauteur 1. La théorie de Cormen donne 10 / (2 ^ (1 + 1)) = 3 (CEIL) tandis qu'il y a 4 nœuds à hauteur 1. Il s'agit d'une contradiction.
Cette formule est fausse, elle donne de mauvaises réponses dans de nombreux cas comme dans cette question pour H = 1 (c'est-à-dire le deuxième niveau de dernier niveau), il donne un nombre maximal de nœuds est 3 mais il y a 4 nœuds. Considérons également un arbre avec 4 nœuds: nœud D a la hauteur 0, envisagons de la hauteur = 1 à l'aide de la formule N / 2 ^ (H + 1) Nous obtenons 4/2 ^ (1 + 1) = 1 ce qui signifie que ce niveau peut avoir au plus 1 noeud qui est faux! de sorte que cette formule n'est donc pas bonne .
La formule est tout à fait correcte. Rien ne va mal avec la formule !! Prenons l'arbre (bien que ce ne soit pas encore en tas, c'est complet) dans la question posée par Nishant sur le dessus. Pour h = 0 signifie toutes les feuilles de ceil (10/2 ^ (0 + 1) = 5) donc il y a 5 feuilles Pour H = 1 signifie tous les nœuds qui ont un arc à atteindre les feuilles, donc ceil (10/2 ^ (1 + 1)) = 3 Il y a 3 de ces nœuds dans votre arbre. Pour H = 2, tous les nœuds qui ont deux arcs consécutifs pour atteindre les feuilles, donc ceil (10/2 ^ (2 + 1)) = 1 afin que vous ne disposez que d'un de ces noeuds (successeur gauche de la racine) Pour H = 3 signifie tous les nœuds qui ont trois arcs à feuilles, donc ceil (10/2 ^ (3 + 1)) = 1 qui est la racine.
La morale de l'histoire est que vous êtes confondu entre la hauteur et le niveau. Le niveau commence à partir de haut en bas. Ce qui signifie que vous avez 4 nœuds au niveau 2. I.E Vous pouvez atteindre 4 nœuds si vous commencez à la racine et déplace deux arcs vers le bas. Alors que la hauteur est complètement différente. Comme dans le cas ci-dessus à la hauteur 0, il y a 5 nœuds (3 sur niveau 3 et 2 au niveau 2). D'où la hauteur H d'un nœud N signifie combien d'arcs vous pouvez vous rendre pour atteindre une feuille.
Cordialement,
J'espère qu'il clarifie le point.
Safdar du Pakistan
lire toutes les réponses, j'ai réalisé que la confusion provient de la définition précise de la hauteur. Dans la page 153 du livre CLRS, la hauteur est définie comme suit:
Affichage d'un tas en tant qu'utile, nous définissons la hauteur d'un nœud dans un tas pour être le nombre d'arêtes sur le trajet
le plus long simple du nœud à une feuille à une feuille ... Regardons maintenant le tas d'origine fourni par Nishant. Les nœuds 8, 9, 10, 6 et 7 sont en hauteur 0 (c'est-à-dire des feuilles). Les nœuds 4, 5 et 3 sont en hauteur 1. Par exemple, il y a un bord entre le nœud 5 et sa feuille, nœud 10. Il existe également un bord entre le nœud 3 et son nœud de feuille 6. Le nœud 6 semble être à Hauteur 1 mais il est en hauteur 0 et donc une feuille. Le nœud 2 est le seul nœud à la hauteur 2. Vous pouvez vous demander que le nœud 1 (la racine) est à deux bords du nœud 6 et 7 (feuilles) et dites que le nœud 1 est également en hauteur 2. Mais si nous regardons en arrière le Définition, le mot audacieux «le plus long» suggère que le plus long chemin approfondi vers le bas de la racine à une feuille a 3 bords (noeud de passage 2). Enfin, le nœud 1 est en hauteur 3.
En résumé, il y a 5, 3, 1, 1 nœuds à hauteur 0, 1, 2, 3, respectivement.
Appliquez la formule à l'observation que nous avons faite dans le paragraphe ci-dessus. Je tiens à souligner que la formule donnée par Nishant n'est pas correcte.
Ça devrait être plafond (N / 2 ^ (H + 1)) Non plafond (n / (2 ^ h + 1). Désolé pour la terrible formatage. Je ne suis pas en mesure de poster une image encore.
Quoi qu'il en soit, en utilisant la formule correcte,
h = 0, plafond (10/2) = 5 (nœuds 8, 9, 10, 6 et 7)
H = 1, plafond (10/4) = 3 (nœuds 4, 5 et 3)
H = 2, plafond (10/8) = 2 (noeud 2, mais c'est correct car la formule prédigne qu'il existe au maximum 2 nœuds à la hauteur 2.)
H = 3, plafond (10/16) = 1 (noeud 1)
Avec la définition correcte de la hauteur, la formule fonctionne.
Il n'est pas vrai que Thomas H. Cormen comptage la hauteur de l'arbre à partir d'une, la hauteur est et dans la formule suivante, il a ajouté 1 plus la hauteur:
Toute la confusion provient du fait que cela fonctionnera bien avec arbres binaires parfaits , pas avec celui que vous montrez dans votre question, c'est pourquoi il est pourquoi il dit Lorsque vous considérez grand-o cela ne compterait pas vraiment 
Pas que cela compte pour la question, mais l'arbre de votre question n'est pas un tas.
SEPP2K, Yaa Vous êtes correct après appliquant le tas de sous-programme, il deviendra un tas binaire, mais ma question est différente, je demande autant de nœuds à la hauteur h.