Dans CLRS, troisième édition, à la page 155, il est indiqué que dans MAX-HEAPIFY,
Les sous-arbres des enfants ont chacun une taille d’au plus 2n / 3. Le pire des cas se produit lorsque le niveau inférieur de l’arbre est à moitié plein.
- Comment puis-je trouver la médiane des nombres dans le temps linéaire en utilisant des tas?
- Un meilleur moyen pour une boucle Python 'for'
- Evaluation paresseuse et complexité temporelle
- Est-ce que 2 ^ n et n * 2 ^ n sont dans la même complexité de temps?
- Un algorithme O (n) peut-il dépasser O (n ^ 2) en termes de temps de calcul?
Je comprends pourquoi c’est pire quand le niveau inférieur de l’arbre est à moitié plein. Et il est également répondu dans cette question au pire des cas dans MAX-HEAPIFY: “le pire des cas se produit lorsque le niveau inférieur de l’arbre est exactement à moitié plein”
Ma question est de savoir comment obtenir 2n / 3?
Pourquoi si le niveau inférieur est à moitié plein, la taille de l’arbre enfant est de 2n / 3?
Comment calculer ça?
Merci
Dans un arbre où chaque nœud a exactement 0 ou 2 enfants, le nombre de nœuds avec 0 enfant est supérieur au nombre de nœuds avec 2 enfants. {Explication: le nombre de nœuds à la hauteur h est 2 ^ h formule de sommation d’une série géomésortingque égale (sum des nœuds de hauteur 0 à h-1) + 1; et tous les nœuds de la hauteur 0 à h-1 sont les nœuds avec exactement 2 enfants}
ROOT LR / \ / \ / \ / \ ----- ----- *****
Soit k le nombre de nœuds dans R. Le nombre de nœuds dans L est k + (k + 1) = 2k + 1. Le nombre total de nœuds est n = 1 + (2k + 1) + k = 3k + 2 (racine plus L plus R). Le rapport est (2k + 1) / (3k + 2), qui est limité par 2/3. Pas de constante inférieure à 2/3, car la limite de k à l’infini est 2/3.
Understand the maximum number of elements in a subtree happens for the left subtree of a tree that has the last level half full.Draw this on a piece of paper to realize this.
Une fois que cela est clair, la limite de 2N / 3 est facile à obtenir.
Supposons que le nombre total de nœuds dans l’arbre est N.
Nombre de nœuds dans l’arborescence = 1 + (nombre de nœuds dans le sous-arbre gauche) + (nombre de nœuds dans le sous-arbre droit)
Pour notre cas où l’arbre a le dernier niveau à moitié plein, nous supposons que le sous-arbre de droite est de hauteur h, alors que le sous-arbre de gauche est de hauteur (h + 1):
Nombre de nœuds dans le sous-arbre gauche = 1 + 2 + 4 + 8 …. 2 ^ (h + 1) = 2 ^ (h + 2) -1 ….. (i)
Nombre de nœuds dans le sous-arbre de droite = 1 + 2 + 4 + 8 …. 2 ^ (h) = 2 ^ (h + 1) -1 ….. (ii)
Ainsi, twigr:
Nombre de nœuds dans l’arborescence = 1 + (nombre de nœuds dans le sous-arbre gauche) + (nombre de nœuds dans le sous-arbre droit)
=> N = 1 + (2^(h+2)-1) + (2^(h+1)-1)
=> N = 1 + 3*(2^(h+1)) - 2
=> N = 3*(2^(h+1)) -1
=> 2^(h+1) = (N + 1)/3
En intégrant cette valeur dans l’équation (i), on obtient:
Number of nodes in Left Subtree = 2^(h+2)-1 = 2*(N+1)/3 -1 =(2N-1)/3 < (2N/3)
Par conséquent, la limite supérieure du nombre maximal de nœuds dans un sous-arbre pour un arbre avec N nœuds est 2N / 3.
Pour un arbre binary complet de hauteur h
, le nombre de nœuds est f(h) = 2^h - 1
. Dans le cas ci-dessus, nous avons un arbre binary presque complet avec le fond à moitié plein. Nous pouvons visualiser ceci comme collection de root + left complete tree + right complete tree
. Si la hauteur de l’arbre d’origine est h
, la hauteur de gauche est h - 1
et à droite h - 2
. Donc, l’équation devient
n = 1 + f(h-1) + f(h-2)
(1)
Nous voulons résoudre ci-dessus pour f(h-1)
exprimé en termes de n
f(h-2) = 2^(h-2) - 1 = (2^(h-1)-1+1)/2 - 1 = (f(h-1) - 1)/2
(2)
En utilisant ci-dessus dans (1) nous avons
n = 1 + f(h-1) + (f(h-1) - 1)/2 = 1/2 + 3*f(h-1)/2
=> f(h-1) = 2*(n-1/2)/3
D’où O (2n / 3)
Ajouter à la réponse de Swen. Comment (2k + 1) / (3k + 2) tend à 2/3, quand k tend vers l’infini,
Lim_ (k -> inf) (2k + 1) / (3k + 2) = Lim_ (k -> inf) k (2 + 1 / k) / k (3 + 2 / k) = Lim_ (k -> inf ) (2 + 1 / k) / (3 + 2 / k)
appliquer la limite, et vous obtenez 2/3
Nombre de nœuds à –
La sum de tous les nœuds du niveau 0 au niveau n,
De la règle de sommation des séries géomésortingques, nous soaps que
En substituant x = 2, on obtient
Comme 2 ^ (n + 1) est le nombre total de nœuds au niveau n + 1, on peut dire que le nombre de nœuds avec 0 enfants est supérieur au nombre de nœuds avec 2 enfants.
Maintenant, calculons le nombre de nœuds dans le sous-arbre gauche, l’arbre droit et le total.
Par le raisonnement ci-dessus, nombre de nœuds feuilles dans le sous-arbre gauche ou racine = k + 1. Nombre de nœuds non-feuilles dans le sous-arbre droit de racine = k, l’arbre est dit à moitié plein.
Nombre total de nœuds dans le sous-arbre gauche de root = k + k + 1 = 2k +
C’est la raison de dire que les sous-arbres des enfants ont chacun une taille maximale de 2n / 3.