(rappel) 3.1 Encadrements de la hauteur d'un Arbre Binaire
Les deux cas particuliers
Les deux cas extrêmes sont :
- Arbre binaire filiforme : chaque noeud n'a qu'un seul noeud-fils non vide au maximum.
- Arbre binaire parfait : tous les noeuds possèdent deux noeuds-fils hormis les noeuds de l'étage le plus bas qui sont tous des feuilles.
Un arbre binaire quelconque est situé entre ces deux cas extrêmes. On peut encadrer la hauteur de l'arbre binaire quelconque à l'aide de la formule suivante :
Encadrement avec une profondeur 1 pour la racine
- Arbre binaire complet : h = log2(n+1)
- Arbre binaire filiforme : h = n
Pour un arbre binaire quelconque :
⌈log2(n+1)⌉ ≤ h ≤ n
Les signes ⌈ ⌉ indiquent un arrondi à l'entier supérieur (demi-crochets vers le haut).
>>> import math
>>> math.log2(15+1)
4.0
>>> math.log2(16+1)
4.087462841250339
On voit alors qu'un arbre de 15 noeuds a une hauteur comprise dans [4; 15].
Par contre, avec 16 noeuds, on obtient une hauteur comprise dans [5;16].
C'est normal : avec 15 noeuds, l'arbre peut être parfait. Si on en rajoute un, il faut nécessairement rajouter un étage...
Encadrement avec une profondeur 0 pour la racine
- Arbre binaire complet : h = log2(n+1) - 1
- Arbre binaire filiforme : h = n - 1
Pour un arbre binaire quelconque :
⌈log2(n+1)⌉ - 1 ≤ h ≤ n - 1
Ou encore :
⌊log2(n)⌋ ≤ h ≤ n - 1
Les signes ⌊ ⌋ indiquent un arrondi à l'entier inférieur (demi-crochets vers le bas).
>>> import math
>>> math.log2(15)
3.9068905956085187
>>> math.log2(16)
4.0
On voit alors qu'un arbre de 15 noeuds a une hauteur comprise dans [3; 14].
Par contre, avec 16 noeuds, on obtient une hauteur comprise dans [4;15].
C'est normal : avec 15 noeuds, l'arbre peut être parfait. Si on en rajoute un, il faut nécessairement rajouter un étage...
Ordre de grandeur de la hauteur d'un arbre (à connaître par coeur)
L'ordre de grandeur de la hauteur d'un Arbre Binaire est compris entre log2(n) et n.
