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
Propriétés
- On peut ordonner des données dans un tableau mais l’algorithme de tri le plus rapide, pour un jeu de données aléatoires, est en $O(n \; \log n)$ ;
- On peut accéder à une donnée en $O(1)$ ;
- On peut rechercher une valeur efficacement en utilisant la dichotomie (si le tableau est trié !) : $O(\log n)$ ;
- Supprimer ou insérer une valeur n’est pas très efficace : $O(n)$ (sauf à la fin du tableau).
Dictionnaires
Propriétés
- Accéder à, supprimer et insérer une valeur se fait très efficacement : $O(1)$ ;
- Les données ne sont pas ordonnées.
- 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 $x$, tous les nœuds situés dans le sous-arbre gauche de $x$ ont une valeur inférieure à la valeur du nœud $x$, et tous ceux situés dans son sous-arbre droit ont une valeur supérieure à la valeur du nœud $x$.
- 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)
Réponse
oui
- 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)
Réponse
oui
- 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)
Réponse
Non ! La propriété est bien vérifiée pour la racine mais pas pour le sous-arbre gauche.
La définition est récurisve !
Un ABR est un arbre binaire
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. -
Écrire à nouveau les spécifications des fonctions
taille
,hauteur
etparcours
(parcours infixe).
|
|
|
|
|
|
|
|
- Vérifier que la fonction
parcours
affiche 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
appartient
dont 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
ajoute
dont 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_copie
dont la spécification est
|
|
Écrire le code de cette fonction.
Utilisation d’un arbre binaire de recherche
- Créer la fonction
plus_petit_element
dont la spécification est
|
|
- Créer la fonction
plus_grand_element
dont la spécification est
|
|
- Créer la fonction
est_abr
dont la spécification est
|
|