Résumé 19 - RECHERCHE DANS UN AB

Lien vers l'activité : Recherche dans un AB

Dernière modif. : 30 01 2021

1 - Rappel sur log2 ou lg

• log2(1) = log2(2⁰) = 0
• log2(2) = log2(2¹) = 1
• log2(4) = log2(2²) = 2
• ...
• log2(2^x) = x

2 - Taille et hauteur d'un Arbre Binaire Complet

Définition : un Arbre Binaire Complet est un arbre binaire dont toutes les feuilles sont sur le dernier niveau. Le dernier niveau est donc plein.

Hauteur h : si on considère une hauteur de 0 pour un arbre n'ayant qu'un seul noeud, on peut calculer la hauteur d'un tel arbre possédant une taille de n noeuds à l'aide de la formule suivante (qu'on fournit sous deux formes) :

h = log2(n+1) - 1            h = ⌊log2(n)⌋

Taille n : on peut également faire l'inverse : trouver le nombre de noeuds d'un arbre binaire complet de hauteur 0. Si on considère que la hauteur d'un arbre n'ayant qu'un noeud est 0, on obtient :

n = 2h+1 - 1

3 - Taille et hauteur d'un arbre filiforme

On considère toujours le cas d'une hauteur de 0 pour un arbre n'ayant qu'un unique noeud.

h = n - 1

4 - Encadrement d'un arbre binaire quelconque

Un AB quelconque est nécessairement entre le cas complet et le cas filiforme. Si on considère toujours le cas d'une hauteur 0 pour un arbre n'ayant qu'un unique noeud :

h + 1 ≤ n ≤ 2h+1 - 1            ⌊log2(n)⌋ ≤ h ≤ n - 1

5 - Recherche au hasard dans un Arbre Binaire

Si on ne peut pas orienter la recherche d'un noeud, on doit aller explorer chaque noeud : la recherche est donc linéaire par rapport à la taille de l'arbre.

Coût : on écrira que le coût est en θ(n)

6 - Recherche orientée dans un Arbre Binaire

Si on a un moyen de savoir s'il faut aller à droite, à gauche ou remonter, la recherche d'un noeud va se faire de façon linéaire par rapport à la hauteur de l'arbre.

Coût : on écrira que le coût est en θ(h)

On peut donc écrire que le coût de la recherche orientée va dépendre de la forme de l'arbre binaire :

• Pour un arbre filiforme, on pourra écrire : θ(n)
• Pour un arbre complet, on pourra écrire : θ(log2 n)

7 - Numérotation binaire des noeuds

Un moyen efficace de trouver un noeud pourrait être de lui fournir un numéro binaire.

Chaque noeud porte le "nom" de son parent suivi d'un 0 s'il est à gauche et d'un 1 s'il est à droite.

Avec ce système :

• le fils gauche d'un parent X porte le numéro 2X
• le fils droite d'un parent X porte le numéro 2X+1
• le parent d'un noeud X porte le numéro X // 2 (division euclidienne)

8 - Implémentation de la numérotation binaire

Si on veut implémenter cette idée pour représenter le type abstrait Arbre Binaire, il suffit donc de créer un tableau et de le remplir en fonction des indices.

Exercice : Implémenter sous forme de tableau l'arbre suivant :