A RBRES BINAIRES DE RECHERCHE
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS
Table de symbole
Recherche : opération fondamentale
données : éléments avec clés
Type abstrait d’une table de symboles (symbol table) ou dictionnaire
Objets : ensembles d’objets avec clés
typiquement : clés comparables (abstraction : nombres naturels)
Opérations :
insert(x, D) : insertion de l’élément x dans D
search(k, D) : recherche d’un élément à clé k (peut être infructeuse)
Opérations parfois supportées :
delete(k, D) : supprimer élément avec clé k
select(i, D) : sélection de l’i-ème élément (selon l’ordre des clés)
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS i
Structures de données
structures simples : tableau trié ou liste chaı̂née
arbre binaire de recherche
tableau de hachage (plus tard)
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS ii
Structures simples
liste chaı̂née ou tableau non-trié : recherche séquentielle
temps de Θ(n) au pire (même en moyenne)
tableau trié : recherche binaire
temps de Θ(log n) au pire
tableau trié : insertion/suppression en Θ(n) au pire cas
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS iii
Arbre binaire de recherche
Dans un arbre binaire de recherche, chaque nœud a une clé.
Accès aux nœuds :
gauche(x) et droit(x) pour les enfants de x (null s’il n’y en a pas)
parent(x) pour le parent de x (null pour la racine)
cle(x) pour la clé de nœud x (en général, un entier dans nos discussions)
Déf. Un arbre binaire est un arbre de recherche ssi les nœuds sont énumerés lors
d’un parcours infixe en ordre croissant de clés.
Thm. Soit x un nœud dans un arbre binaire de recherche. Si y est un nœud dans le
sous-arbre gauche de x, alors cle(y) ≤ cle(x). Si y est un nœud dans le sous-arbre
droit de x, alors cle(y) ≥ cle(x).
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS iv
Arbre binaire de recherche — exemple
9
6 12
3 8 11 15
1 4 7 19
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS v
Arbre binaire de recherche (cont)
À l’aide d’un arbre de recherche, on peut implémenter une table de symboles d’une
manière très efficace.
Opérations : recherche d’une valeur particulière, insertion ou suppression d’une
valeur, recherche de min ou max, et des autres.
Pour la discussion des arbres binaires de recherche, on va considérer les pointeurs
null pour des enfants manquants comme des pointeurs vers des feuilles ou nœuds
externes
Donc toutes les feuilles sont null et tous les nœuds avec une valeur cle() sont des
nœuds internes.
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS vi
Min et max
Algo M IN() // trouve la valeur minimale dans l’arbre
1 x ← racine; y ← null
2 tandis que x 6= null faire
3 y ← x; x ← gauche(x)
4 retourner y
Algo M AX() // trouve la valeur maximale dans l’arbre
1 x ← racine; y ← null
2 tandis que x 6= null faire
3 y ← x; x ← droit(x)
4 retourner y
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS vii
Recherche
Algo S EARCH(x, v) // trouve la clé v dans le sous-arbre de x
F1 si x = null ou v = cle(x) alors retourner x
F2 si v < cle(x)
F3 alors retourner S EARCH(gauche(x), v)
F4 sinon retourner S EARCH(droit(x), v)
Maintenant, S EARCH(racine, v) retourne
- soit un nœud dont la clé est égale à v,
- soit null.
Notez que c’est une recursion terminale ⇒ transformation en forme itérative
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS viii
Recherche (cont)
Solution itérative (plus rapide) :
Algo S EARCH(x, v) // trouve la clé v dans le sous-arbre de x
F1 tandis que x 6= null et v 6= cle(x) faire
F2 si v < cle(x)
F3 alors x ← gauche(x)
F4 sinon x ← droit(x)
F5 retourner x
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS ix
Recherche — efficacité
Dans un arbre binaire de recherche de hauteur h :
M IN() prend O(h)
M AX() prend O(h)
S EARCH(racine, v) prend O(h)
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS x
Insertion
On veut insérer une clé v
Idée : comme en S EARCH, on trouve la place pour v (enfant gauche ou droit
manquant)
9
6 12
3 8 11 15
1 4 7 19
14
insertion de «14»
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS xi
Insertion (cont.)
insertion — pas de clés dupliquées
Algo I NSERT(v) // insère la clé v dans l’arbre
I1 x ← racine
I2 si x = null alors initialiser avec une racine de clé v et retourner
I3 tandis que vrai faire // (conditions d’arrête testées dans le corps)
I4 si v = cle(x) alors retourner // (pas de valeurs dupliquées)
I5 si v < cle(x)
I6 alors si gauche(x) = null
I7 alors attacher nouvel enfant gauche de x avec clé v et retourner
I8 sinon x ← gauche(x)
I9 sinon si droit(x) = null
I10 alors attacher nouvel enfant droit de x avec clé v et retourner
I11 sinon x ← droit(x)
ABR ? IFT2015 H2007 ? U DE M ? M IKL ÓS C S ŰR ÖS xii
