Discussion :

[Revaroa]

Bonjour,

J'ai un problème qui est de montrer qu'un tas binaire de n éléments a une hauteur de log(n).

Voici ce que j'ai fait mais je suis pas sûr que c'est correct.

On sait que le nombre d'éléments n dans un tas binaire est : 2^h+1 -1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
2^h+1 -1 = n
log(2^h+1 -1) = log(n)
(h+1) * log(2) - 1 = log(n)
h+1 * 1 - 1 = log(n)
h=log(n)

Merci d'avance.

[François DORIN]

Bonsoir,

Avec les parenthèses, cela serait mieux [CODEILINE]n = 2^(h+1)-1[/CODEINLINE].

Maintenant, si j'ai bien compris, ce que tu souhaites, c'est ayant n, comment trouver h ?

Simple :

n = 2^(h+1) - 1
n + 1 = 2^(h+1)
log(n + 1) = log(2^(h+1))
log(n + 1) = (h+1) log(2)
log(n + 1) / log(2) = h + 1
d'où h = log(n + 1) / log(2) - 1

[Revaroa]

Merci pour la réponse rapide.

Pour résoudre le problème, je me suis dis que peut-être si l'on part de n on pourrait arriver au résultat.
Pour cela, j'ai donc supposé que l'on connait n qui vaut : n = 2^(h+1) - 1
J'ignore si c'est de cette façon qu'on doit le faire. Mais on dirait qu'on arrive à quelque chose.

Pour le calcul
Est ce que : h = log(n + 1) / log(2) - 1
signifie que le tas a une hauteur de log(n) ?

Désolé, si c'est une question bête.

[François DORIN]

Pour le calcul
Est ce que : h = log(n + 1) / log(2) - 1
signifie que le tas a une hauteur de log(n) ?

Non, cela signifie que la hauteur vaut log(n + 1) / log(2) - 1

[tbc92]

Tu peux le vérifier sur un exemple numérique :
h = 10, tu peux construire un arbre de 511 éléments. Est-ce que log(511) = 10 ? non.
En fait, je crois que tu as mal recopié l'énoncé de l'exercice :
Tu as écrit :
J'ai un problème qui est de montrer qu'un tas binaire de n éléments a une hauteur de log(n).
Je crois que l'énoncé correct est plutôt :
J'ai un problème qui est de montrer qu'un tas binaire de n éléments a une hauteur en log(n).

[anapurna]

Salut

comment tu trouve 512 éléments pour une hauteur de 10 ?
reprenons ça formule pour le calcul

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

n = 2^(h+1) - 1 =>( 2^(8+1)) -1 = 512 -1  => 511

je vois pas bien ou intervient la valeur 10
pour trouver ta hauteur avec le n

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

=(LOG(n+1)/LOG(2)) - 1  =>  (LOG(511+1)/LOG(2))-1 =>  9 -1 => 8