Arbres binaires de recherche [br]
Algorithmique
Karine Zampieri, Stéphane Rivière
Unisciel algoprog Version 21 mai 2018
Table des matières
1 Définition, Parcours, Représentation 2
2 Recherches 4
2.1 Recherche d’un élément . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Minimum et maximum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Successeur et prédécesseur . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Insertion d’un élément 8
4 Suppression d’un élément 9
5 Conclusion 12
Arbres binaires de recherche
Mots-Clés Arbres binaires de recherche
Requis Axiomatique impérative, Récursivité des actions, Complexité des algorithmes,
Arbres enracinés
Difficulté • • ◦
Introduction
Un arbre binaire de recherche est une structure de donnée qui permet de représen-
ter un ensemble de valeurs si l’on dispose d’une relation d’ordre sur ces valeurs. Les
opérations caractéristiques sont l’insertion, la suppression et la recherche d’une valeur.
Ces opérations sont peu coûteuses si l’arbre n’est pas trop déséquilibré. En pratique, les
valeurs sont des clés permettant d’accéder à des enregistrements.
Ce module les décrit puis définit les opérations caractéristiques (recherche, insertion,
suppression).
1
, Unisciel algoprog – br00cours-texte, May 21, 2018 2
1 Définition, Parcours, Représentation
Définition d’un ABR
Un arbre binaire de recherche (abrégé ABR) est un arbre binaire vérifiant la propriété
suivante : soient x et y deux noeuds de l’arbre :
• Si y est un noeud du sous-arbre gauche de x alors cle(y) ≤ cle(x)
• Si y est un noeud du sous-arbre droit de x alors cle(y) ≥ cle(x)
Exemple
L’arbre suivant est un ABR : 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.
Remarque
La définition suppose donc qu’une valeur n’apparaı̂t au plus qu’une seule fois dans un
arbre de recherche.
Attention
Bien que différents, ces deux arbres ABR contiennent exactement les mêmes valeurs.
15 15
6 18 6 17
3 7 17 20 3 7 18
2 4 13 2 4 13 20
9 9
Algorithmique
Karine Zampieri, Stéphane Rivière
Unisciel algoprog Version 21 mai 2018
Table des matières
1 Définition, Parcours, Représentation 2
2 Recherches 4
2.1 Recherche d’un élément . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Minimum et maximum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Successeur et prédécesseur . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Insertion d’un élément 8
4 Suppression d’un élément 9
5 Conclusion 12
Arbres binaires de recherche
Mots-Clés Arbres binaires de recherche
Requis Axiomatique impérative, Récursivité des actions, Complexité des algorithmes,
Arbres enracinés
Difficulté • • ◦
Introduction
Un arbre binaire de recherche est une structure de donnée qui permet de représen-
ter un ensemble de valeurs si l’on dispose d’une relation d’ordre sur ces valeurs. Les
opérations caractéristiques sont l’insertion, la suppression et la recherche d’une valeur.
Ces opérations sont peu coûteuses si l’arbre n’est pas trop déséquilibré. En pratique, les
valeurs sont des clés permettant d’accéder à des enregistrements.
Ce module les décrit puis définit les opérations caractéristiques (recherche, insertion,
suppression).
1
, Unisciel algoprog – br00cours-texte, May 21, 2018 2
1 Définition, Parcours, Représentation
Définition d’un ABR
Un arbre binaire de recherche (abrégé ABR) est un arbre binaire vérifiant la propriété
suivante : soient x et y deux noeuds de l’arbre :
• Si y est un noeud du sous-arbre gauche de x alors cle(y) ≤ cle(x)
• Si y est un noeud du sous-arbre droit de x alors cle(y) ≥ cle(x)
Exemple
L’arbre suivant est un ABR : 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.
Remarque
La définition suppose donc qu’une valeur n’apparaı̂t au plus qu’une seule fois dans un
arbre de recherche.
Attention
Bien que différents, ces deux arbres ABR contiennent exactement les mêmes valeurs.
15 15
6 18 6 17
3 7 17 20 3 7 18
2 4 13 2 4 13 20
9 9
