TD10
Exercice 2
2)
Tous les arbres tassés de taille 6
Tous les arbres tassés de taille 7
Tous les arbres tassés de taille 11
3)
Pour \(n \in \mathbb{N}\) il y a 1 arbre tassé (à gauche) de taille \(n\)
hauteur arbre vide =0
4)
Un arbre tassé de hauteur \(h\) possède n noeud
\(2^{h-1}-1 < n \leq 2^h -1\)
(\(1+2+4+8+16+32+...+2^{h-2} = 2^{h-1}-1\))
- \(2^{h-1} -1 < n\)
\(\iff 2^{h-1} < n+1\)
\(\iff h-1 < log_2(n+1)\)
\(\iff h < log_2(n+1) + 1\)
- \(n \leq 2^h-1\)
\(\iff n+1 \leq 2^h\)
\(log_2(n+1) \leq h\)
- \(log_2(n+1) \leq h < log_2(n+1) + 1\)
Exercice 3
A :
B :
| 4 | 5 | 9 | ||||
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
-> Pas un arbre tournoi
Exercice 4
\(fd(i) = 2 * i+2\)
\(fg(i) = 2 * i +1\)
\(p(i) =\) si \(i\) pair, \(i/2 -1\)
si \(i\) impair \((i-1)/2\)
Exercice 5
Arbre tournoi
La racine contient une des plus petites étiquettes.
Exercice 6
| 4 | 13 | 20 | 14 | 20 | 20 | ||||
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Complexité temps retrait : \(O(log_2(n))\) Complexité temps ajout : \(O(log(n))\)