Le pire des cas dans Max-Heapify – Comment obtenez-vous 2n / 3?

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 à –

• niveau 0 ie la racine est 2 ^ 0
• le niveau 1 est 2 ^ 1
• le niveau 2 est 2 ^ 2
• …
• le niveau n est 2 ^ n

La sum de tous les nœuds du niveau 0 au niveau n,

• S = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + … + 2 ^ n

De la règle de sommation des séries géomésortingques, nous soaps que

• x ^ 0 + x ^ 1 + x ^ 2 + … + x ^ (n) = (x ^ (n + 1) – 1) / (x-1)

En substituant x = 2, on obtient

• S = 2 ^ (n + 1) – 1. soit 2 ^ (n + 1) = S + 1

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.

• Supposons que le nombre de nœuds non-feuille dans le sous-arbre gauche de root = k.

• 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 +

• Nombre total de nœuds dans l’arbre, n = (2k + 1) + k + 1 = 3k + 2.
• Rapport des nœuds dans le sous-arbre de gauche et des nœuds totaux = (2k + 1) / (3k + 2) qui est limité par 2/3.

C’est la raison de dire que les sous-arbres des enfants ont chacun une taille maximale de 2n / 3.