Arbres Binaires Recherche
Introduction
Quelle structure de données permet :
- d’organiser les données selon un ordre donné (numérique, lexicographique, etc.) ;
- d’effectuer des recherches le plus efficacement possible ;
- d’accéder à, d’insérer ou de supprimer les données le plus efficacement possible.
Tableaux
Dictionnaires
- Remarque
- Dans la suite de ce document, on considérera que les valeurs des nœuds sont des entiers.
Un arbre binaire de recherche, ou ABR, est un arbre binaire avec la propriété suivante : quel que soit le nœud , tous les nœuds situés dans le sous-arbre gauche de ont une valeur inférieure à la valeur du nœud , et tous ceux situés dans son sous-arbre droit ont une valeur supérieure à la valeur du nœud .
- Remarque
- La définition précédente est récursive.
-
Cet arbre binaire est-il un arbre binaire de recherche ?
graph TD A(3) --- B(1) B --- C(None) B --- D(2) D --- E(None) D --- F(None) A --- G(4) G --- H(None) G --- I(None) -
Cet arbre binaire est-il un arbre binaire de recherche ?
graph TD A(3) --- B(2) B --- C(1) C --- D(None) C --- E(None) B --- F(None) A --- G(4) G --- H(None) G --- I(None) -
Cet arbre binaire est-il un arbre binaire de recherche ?
graph TD A(3) --- B(2) B --- C(None) B --- D(1) D --- E(None) D --- F(None) A --- G(4) G --- H(None) G --- I(None)
Les ABR servent à maintenir un ensemble de valeurs ordonnées, avec une meilleure complexité qu’une liste chaînée par exemple. On commence par la recherche d’un élément. La structure de l’ABR permet d’éviter de le parcourir en entier.
Un ABR est un arbre binaire
Le paradigme de programmation utilisé ci-dessous est le paradigme impératif : on crée dans un premier temps une structure élémentaire à l’aide d’une classe et on définit ensuite des fonctions qui manipulent cette structure.
On ne crée pas de structure arbre binaire (accompagnée de méthodes).
-
Pour représenter un ABR, on va à nouveau utiliser la classe
Noeud. Écrire à nouveau le code de cette classe.
Les contraintes sur les valeurs des nœuds ne sont pas codées dans la classe. -
À quel arbre binaire de recherche ce code correspond-il ?
- Écrire à nouveau les spécifications des fonctions
taille,hauteuretparcours(parcours infixe).
- Vérifier que la fonction
parcoursaffiche les valeurs dans l’ordre croissant.
- Rappel
- On peut voir le parcours infixe comme la projection de l’arbre sur une droite.
Recherche dans un ABR
- Écrire le code de la fonction
appartientdont la spécification est
- Quelle est la complexité de cette recherche ?
Ajout d’une valeur dans un ABR
-
Envisager un ABR et, à la main, ajouter un élément.
-
Quel peut-être le code de la fonction
ajoutedont la spécification est
-
Quelle est la complexité de cette fonction ?
-
Pour résoudre le problème de l’ajout d’une valeur à un arbre initialement vide et/ou pour ne pas modifier un arbre déjà constitué, il est possible de programmer la fonction
ajoute_copiedont la spécification est
Écrire le code de cette fonction.
Utilisation d’un arbre binaire de recherche
- Créer la fonction
plus_petit_elementdont la spécification est
- Créer la fonction
plus_grand_elementdont la spécification est
- Créer la fonction
est_abrdont la spécification est
Corrigé
Corrigé de l'activitéÀ retenir
Un arbre binaire de recherche est un arbre binaire contenant des valeurs ordonnées, tel que tout nœud contient une valeur plus grande (respectivement plus grande ou égale) que les valeurs de tous les nœuds situés dans son sous-arbre gauche. Cette organisation permet de procéder par dichotomie, en n’ayant à considérer qu’un seul sous-arbre pendant une opération. Lorsqu’ils sont équilibrés, les arbres binaires de recherche constituent une méthode très efficace pour stocker et rechercher de l’information.