Arbres binaires
Chap III: Structures arborescentes
Recherche d’un élément
§ DFS : Depth-First Search ou recherche en profondeur d’abord
! Avec DFS, on n’a besoin
On cherche à la racine, si l’élément n’y est pas: d’aucun stockage en plus mais
- On cherche dans le fils gauche o n p e u t s ’ a t t a rd e r t ro p
longtemps dans une branche.
- S’il n’est pas dans le fils gauche, on cherche dans le fils droit
=> La recherche s’arrête quand on a trouvé ou qu’il n’y a plus de
branches à explorer.
=> Un fonctionnement récursif
§ BFS : Breadth-First Search ou recherche en largeur
d’abord
! Avec BFS, on fonctionne
On cherche à la racine, si l’élément n’y est pas : par profondeur incrémentale
donc on évite le piège mais on
- On cherche dans les nœuds de profondeur 1 a besoin d’un stockage dont la
- S’il n’est pas dans à la profondeur 1, on cherche à la taille augmente à chaque
étape.
profondeur 2, …
=> Un fonctionnement itératif
© [Link]
12
Arbres binaires
Chap III: Structures arborescentes
Recherche d’un élément: DFS
DFS : Depth-First Search ou recherche en profondeur d’abord
Exemples:
• Chercher la valeur 4
- Racine=1 => non • Chercher la valeur 3
// passer au fils gauche - Racine=1 => non
- Racine=2 => non // passer au fils gauche
// passer au fils gauche - Racine=2 => non
- Racine =4 => Trouvé // passer au fils gauche
- Racine =4 => non
- Pas de fils
- Pas de fils droite
// passer au fils droit
- Racine=3 => Trouvé
! Si l’élément est dans le sous arbre droit de la racine, on va quand même explorer
tout le sous-arbre de gauche
© [Link]
13
Arbres binaires
Chap III: Structures arborescentes
Recherche d’un élément: BFS
BFS : Breadth-First Search ou recherche en largeur d’abord
On va avoir besoin d’une file FIFO (ou autre
Exemples 1:
structure équivalente) pour stocker les nœuds à
• Chercher la valeur 3
explorer.
- File=[arbre (1)]
• Au début, la file contient l’arbre principal
- Racine=1 => non
(racine)
//On défile l’arbre(1) et on enfile ses 2 sous-
• Si la valeur n’est pas à la racine du premier arbres
arbre de la file - File= [sous-arbre gauche (1), sous-arbre
- On supprime l’arbre de la file droit (1)
- On ajoute ses deux sous-arbre en fin de file - Racine=2 => non
s’ils ne sont pas vides
//On défile la racine 2 et on enfile ses sous-
- Et on explore l’arbre suivant, qui est le arbres
premier de la file
• On s’arrête quand on a trouvé ou que la file est - File= [sous-arbre droite (1), sous-arbre
vide gauche (2)]
- Racine =3 => Trouvé
© [Link]
14
Arbres binaires
Chap III: Structures arborescentes
Recherche d’un élément: BFS
BFS : Breadth-First Search ou recherche en largeur d’abord
Exemple 2:
• Chercher la valeur 4
- File=[arbre (1)]
- Racine=1 => non
//On défile l’arbre(1) et on enfile ses 2 sous-arbres
- File= [sous-arbre gauche (1), sous-arbre droit (1)
- Racine=2 => non
//On défile la racine 2 et on enfile ses sous-arbres
- File= [sous-arbre droite (1), sous-arbre gauche (2)]
- Racine =3 => non
//On défile la racine 3 et on enfile ses sous-arbres
- File= [sous-arbre gauche (2), sous-arbre gauche (3), sous-arbre droit (3)]
- Racine=4 => Trouvé
© [Link]
15
2. Arbres binaires de recherche
16
Chap III: Structures arborescentes
Arbres binaires de recherche
• Un arbre binaire de recherche (ou ABR) est une structure de donnée qui permet de représenter
un ensemble de valeurs si l’on dispose d’une relation d’ordre sur ces valeurs.
• Les opérations caractéristiques sur les arbres binaires de recherche sont l’insertion, la
suppression, et la recherche d’une valeur.
• Ces opérations sont peu couteuses si l’arbre n’est pas trop déséquilibré.
=> En pratique, les valeurs sont des clés permettant d’accéder à des enregistrements.
Exemple:
• Soit E un ensemble muni d’une relation
d’ordre, et soit A un arbre binaire portant
des valeurs de E.
• L’arbre A est un arbre binaire de recherche
si pour tout noeud p de A, la valeur de p est
strictement plus grande que les valeurs
figurant dans son sous-arbre gauche et
strictement plus petite que les valeurs
figurant dans son sous-arbre droit.
=> Cette définition suppose donc qu’une valeur
n’apparaît au plus qu’une seule fois dans un arbre de
recherche.
© [Link] Source: 3
17
Chap III: Structures arborescentes
Arbres binaires de recherche
• Pour accéder à la clé la plus petite dans un ABR il suffit de descendre sur le fils gauche
autant que possible. Le dernier noeud visité, qui n’a pas de fils gauche, porte la valeur la plus
petite de l’arbre.
• Pour accéder à la clé la plus grande dans un ABR il suffit de descendre sur le fils droit autant
que possible. Le dernier noeud visité, qui n’a pas de fils droit, porte la valeur la plus grande
de l’arbre.
• Exemple: Le parcours infixé de l’arbre produit la suite ordonnée des clés
⇒ 7, 8, 9, 16, 17, 21, 22, 23, 25, 26, 27, 28, 29,
30, 32, 34, 35, 36, 37 ...
Source: 3
© [Link] Source: 3
18
Arbres binaires de recherche
Chap III: Structures arborescentes
Recherche d’une valeur
• La recherche d’une valeur dans un ABR consiste à parcourir une branche en partant de la
racine, en descendant chaque fois sur le fils gauche ou sur le fils droit suivant que la clé
portée par le noeud est plus grande ou plus petite que la valeur cherchée.
• La recherche s’arrête dès que la valeur est rencontrée ou que l’on a atteint l’extrémité d’une
branche (le fils sur lequel il aurait fallu descendre n’existe pas).
Source: 3
© [Link]
19
Arbres binaires de recherche
Chap III: Structures arborescentes
Recherche d’une valeur
Version itérative
Fonction rechercheAbr(a:ArbreBinaire , v: Info): Booléen
Va:arbrebinaire
vtrouver: Booléen
DEBUT
Vtrouver <-VRAI
Va <-a
TANTQUE (Vide(va)=FAUX ET v <> Info(va)) FAIRE
SI v < Info(va) ALORS
va <- FilsGauche(va)
SINON
va <- FilsDroit(va)
FINSI
FINTANTQUE
SI Vide(va)=VRAI ALORS
vtrouver <-FAUX
FINSI
RETOURNER vtrouver
FIN
© [Link]
20
Arbres binaires de recherche
Chap III: Structures arborescentes
Recherche d’une valeur
Version récursive
Fonction rechercheAbr(a:ArbreBinaire , v: Info): Booléen
DEBUT
SI vide(a)=VRAI ALORS
RETOURNER Faux
SINON
SI v=Info(a) ALORS
RETOURNER Vrai
SINON
SI v < Info(a) ALORS
RETOURNER rechercheAbr (FilsGauche(a),v)
SINON
RETOURNER rechercheAbr (FilsDroite(a),v)
FINSI
FINSI
FINSI
FIN
© [Link]
21
Arbres binaires de recherche
Chap III: Structures arborescentes
Insertion d’une valeur
• Le principe est le même que pour la recherche. Un nouveau noeud est créé avec la nouvelle
valeur et insérée à l’endroit où la recherche s’est arrêtée.
• Exemple: Insérer la valeur 31
Source: 3
© [Link]
22
Arbres binaires de recherche
Chap III: Structures arborescentes
Insertion d’une valeur
Version récursive
Procedure InsertionAbr(a:abrR , v: Info)
DEBUT
SI vide(a)=VRAI ALORS
a<-CreerArbre(v, NIL, NIL)
SINON
SI v < Info(a) ALORS
InsertionArb(FilsGauche(a),v)
SINON
SI v > Info(a) ALORS
InsertionArb(FilsDroite(a),v)
FINSI
FINSI
FINSI
FIN
© [Link]
23
