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

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.

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

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