Arbre binaire de recherche : définition et mise en oeuvre en C++
Les listes chaînées, les piles et les files d'attente sont des collections linéaires ; un arbre est une collection non linéaire. Dans un arbre général, chaque nœud peut avoir deux liens ou plus vers d'autres nœuds. Bien que les arbres généraux aient de nombreuses applications en informatique (comme les répertoires), nous rencontrons davantage d'arbres binaires, c'est-à-dire des arbres comportant un maximum de deux sous-arbres. Un cas particulier d'arbre binaire est appelé arbre binaire de recherche dans lequel les valeurs des nœuds du sous-arbre de gauche sont inférieures à la valeur de la racine, et les valeurs du sous-arbre de droite sont supérieures à la valeur de la racine. La figure ci-dessous montre un arbre binaire de recherche.
Parcours d'arbre binaire
Le parcours d'un arbre binaire de recherche exige que chaque nœud de l'arbre soit traité une fois et une seule dans une séquence prédéterminée. Il existe trois types de traversées : préfixe, postfixe et infixe.
Parcours infixe
Dans le parcours dans l'ordre, le traitement de la racine se situe entre les deux sous-arbres. En d'autres termes, nous devons d'abord parcourir tout le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Cette règle doit être suivie dans chaque sous-arbre. Le parcours infixe de l’arbre de la figure ci-dessus nous donne la séquence suivante. La racine de l'arbre entier vient au milieu. Notez que dans le parcours infixe d'un arbre de recherche binaire, les valeurs sont traitées dans l'ordre croissant.
Parcours préfixe
Dans le parcours préfixe, le nœud racine est traité en premier, suivi de tous les nœuds du sous-arbre gauche parcourus en préfixe, puis de tous les nœuds du sous-arbre droit parcourus en préfixe. Le parcours préfixe de l’arbre de la figure ci-dessus nous donne la séquence suivante. Notez que la racine se trouve au début.
Parcours postfixe
Dans le parcours post-ordre, le traitement de la racine vient après le traitement de deux sous-arbres. En d'autres termes, nous devons d'abord parcourir le sous-arbre gauche, puis le sous-arbre droit et enfin la racine. Cette règle doit être suivie dans chaque sous-arbre. Le parcours post-ordre de l'arbre de la figure ci-dessus nous donne la séquence suivante. Notez que la racine de l'arbre entier se trouve à la fin.
Mise en oeuvre
Nous avons discuté trois parcours pour un arbre binaire de recherche (ABR). Lorsqu'un ABR est implémenté correctement, les valeurs des données dans l’ABR sont triées, ce qui signifie que nous pouvons rechercher plus facilement l'arbre (d'où le nom arbre binaire de recherche). Les trois parcours nous aident à construire un ABR, à rechercher un ABR et à détruire un ABR. Cependant, pour chaque problème, nous devons utiliser le bon parcours.
Classe ABR
Dans notre définition, nous définissons un nœud avec des attributs d'arbre, les données stockées dans le nœud donnees et deux pointeurs gauche (sous-arbre gauche) et droit (sous-arbre droit), dans certains livres comme "Algorithmique" écrit par Cormen, leiserson et d'autres, ils utilisent également un attribut parent pour référencer le parent de chaque nœud, mais dans notre définition, nous n'utilisons pas le parent et adaptons nos fonctions pour récupérer le parent si nécessaire.
Ce qui suit est la définition de la classe ABR :
Classe ABR
#ifndef ABR_H #define ABR_H #include <iostream> using namespace std; // Définition du noeud en tant que struct template <typename T> struct Noeud { T donnees; Noeud <T>* gauche; Noeud <T>* droit; }; // Définition de la classe Liste template <class T> class ABR { private: Noeud <T>* racine; int compteur; Noeud <T>* CreerNoeud (const T& valeur); void detruire (Noeud <T>* ptr); // Fonction d'aide void inserer (const T& value, Noeud <T>*& ptr); // Fonction d'aide void infixe (Noeud <T>* ptr) const; // Fonction d'aide void prefixe (Noeud <T>* ptr) const; // Fonction d'aide void postfixe (Noeud <T>* ptr) const; // Fonction d'aide Noeud <T>* successeur (Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide Noeud <T>* predecesseur (Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide void supprimer (Noeud <T>* ptr, Noeud <T>* parent); // Fonction d'aide Noeud <T>* recherche (const T& value, Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide public: ABR (); ~ABR (); void inserer (const T& value); void detruire (); void supprimer (const T& value); Noeud <T>* recherche (const T& value) const; void infixe () const; void prefixe () const; void postfixe () const; int taille () const; bool estVide () const; }; #endif
Pour les méthodes utilisées dans la classe nous les avons divisées en deux catégories ; les méthodes privées utilisées comme aide pour effectuer les actions réelles, et les méthodes publiques utilisées pour appeler les méthodes privées sans connaître la définition et la mise en œuvre réelles.
Dans les sections suivantes, nous discuterons de la mise en œuvre de chaque méthode en détail.
Le constructeur
Le constructeur initie la racine de l'ABR à NULL (ou 0) et compteur à 0.
// Constructeur template <class T> ABR <T> :: ABR():racine (0), compteur (0){}
Le destructeur
Le destructeur utilisé pour supprimer la racine et tous ses nœuds descendants, donc détruire l'arbre. Le destructeur appelle la méthode detruire utilisée pour effectuer le travail réel.
// Destructeur template <class T> ABR <T> :: ~ABR () { detruire(racine); }
Détruire un ABR
Comment détruisons-nous un ABR ? La réponse est que nous le faisons nœud par nœud. Cependant, pour supprimer un nœud, le sous-arbre gauche et le sous-arbre droit doivent être vides. Cela suggère que la destruction d'un ABR nécessite un parcours postfixe car le dernier nœud qui doit être détruit est la racine. Nous devons détruire le sous-arbre gauche, puis détruire le sous-arbre droit, et enfin détruire la racine. Cela signifie que nous pouvons écrire un algorithme récursif comme indiqué ci-dessous :
- Détruire le sous-arbre gauche.
- Détruire le sous-arbre droit.
- Supprimer la racine.
// La fonction d'aide (Récursive) appelée par le destructeur template <class T> void ABR <T> :: detruire (Noeud <T>* ptr) { if (!ptr){return;} detruire (ptr -> gauche); // détruire le sous-arbre gauche detruire (ptr -> droit); // détruire le sous-arbre droit delete ptr; // détruire la racine }
Insertion
Comment insérer des nœuds dans un arbre binaire de recherche ? La réponse est qu'il faut trouver la position du nœud à insérer. La recherche de la position doit commencer à partir de la racine. Il faut insérer la racine puis insérer le sous-arbre gauche ou le sous-arbre droit. Dans chaque sous-arbre, nous faisons la même chose. Cela signifie que nous pouvons écrire un algorithme récursif comme indiqué ci-dessous :
- Si l'arbre est vide, insérez-le en tant que racine.
- Insérer dans le sous-arbre de gauche si la valeur est inférieure à la valeur racine.
- Insérer dans le sous-arbre de droite si la valeur est supérieure à la valeur racine.
// La fonction d'aide (Récursive) appelée par la fonction membre inserer template <class T> void ABR <T> :: inserer (const T& valeur, Noeud <T>*& ptr) { // si l'arbre vide, inserer comme racine if (!ptr){ ptr = CreerNoeud (valeur); return; } // si la valeur est inférieure à la valeur de racine, // insérer le noeud dans le sous-arber gauche else if (valeur < ptr -> donnees){ inserer (valeur, ptr -> gauche); } // Sinon, insérer le noeud dans le sous-arber droit else{ inserer (valeur, ptr -> droit); } }
Rechercher un noeud
La méthode de recherche, est plus simple, on compare la valeur de la clé avec la racine si elle ne correspond pas on continue la recherche dans le sous-arbre gauche ou droit, cette méthode par nature est récursive, voici l'algorithme :
- Si l'arbre est vide, le nœud n’existe pas.
- Si la valeur recherchée égale à la valeur de la racine, retourner la racine
- Rechercher dans le sous-arbre de gauche si la valeur est inférieure à la valeur racine.
- Rechercher dans le sous-arbre de droite si la valeur est supérieure à la valeur racine.
Cette méthode utilisait un paramètre parent (passé par référence) utilisé pour stocker le parent du nœud en question.
// Fonction d'aide (Récursive) appeler par la fonction membre recherche template <class T> Noeud <T>* ABR <T> :: recherche (const T& valeur, Noeud <T>* ptr, Noeud <T>*& parent) const { if (!ptr){ //Arbre est vide return NULL; } else if ((ptr->donnees) == valeur){ // la valeur recherchée est stockée dans la racine return ptr; } else if (valeur < (ptr->donnees)){ parent=ptr; // la valeur recherchée est dans le sous-arbre gauche return recherche (valeur, ptr->gauche, parent); } else{ parent=ptr; // sinon, la valeur recherchée est dans le sous-arbre droit return recherche (valeur, ptr->droit, parent); } }
Successeur d’un noeud.
Cette méthode permet de renvoyer le successeur d’un nœud qui est le nœud avec la valeur minimale dans son sous-arbre droit. Cette méthode utilisée lorsque l'on veut supprimer un nœud avec deux enfants
Cette méthode utilisait un paramètre parent (passé en référence) utilisé pour stocker le parent du nœud en question.
template <class T> Noeud <T>* ABR <T> :: successeur (Noeud <T>* ptr, Noeud <T>*& parent) const{ if (!ptr){return NULL;} Noeud <T>* courant = ptr; while (courant->gauche != 0){ parent = courant; courant = courant -> gauche; } return courant; }
Prédécesseur d’un noeud.
Cette méthode permet de renvoyer le prédécesseur d’un nœud qui est le nœud avec la valeur maximale dans son sous-arbre gauche. Cette méthode utilisée lorsque l'on veut supprimer un nœud avec deux enfants.
Cette méthode utilisait un paramètre parent (passé en référence) utilisé pour stocker le parent du nœud en question.
template <class T> Noeud <T>* ABR <T> :: predecesseur (Noeud <T>* ptr, Noeud <T>*& parent) const{ if (!ptr){return NULL;} Noeud <T>* courant = ptr; while (courant->droit != 0){ parent = courant; courant = courant -> droit; } return courant; }
Supprimer un nœud de l’ABR
L'opération de suppression d’un nœud dans un ABR est plus compliquée que l'ajout et la recherche. Principalement, cette opération peut être divisée en deux étapes :
- Rechercher le nœud à supprimer ;
- Si le nœud est trouvé, exécuter l'algorithme de suppression.
La première étape est identique à l'algorithme de recherche, sauf que nous devons tracer le parent du nœud actuel. La deuxième partie est plus délicate. Il y a trois cas, qui sont décrits ci-dessous.
Le noeud à supprimer n'a pas d'enfants.
Ce cas est assez simple. L'algorithme définit le lien correspondant du parent à NULL et supprime le noeud.
Le noeud à supprimer a un seul enfant.
Dans ce cas, le nœud est coupé de l'arbre et l'algorithme lie l'enfant unique (avec son sous-arbre) directement au parent du nœud supprimé.
Le noeud à supprimer a deux enfants.
C'est le cas le plus complexe. La solution standard est basée sur cette idée : on laisse le nœud à enlever où il est, mais on se débarrasse de sa valeur et on trouve une autre valeur à y stocker. Cette valeur est extraite d'un nœud en dessous du nœud en question, et c'est ce nœud qui est en fait supprimé de l'arbre. Maintenant la question quelle valeur devrions-nous prendre ? Simplement nous trouvons le successeur ou prédécesseur du nœud à supprimer, remplaçons la valeur du nœud en question par la valeur stockée dans le successeur (ou prédécesseur), puis supprimons le successeur (ou prédécesseur).
- Le successeur d'un nœud est un nœud avec une valeur minimale dans son sous-arbre droit
- Le prédécesseur d'un nœud est un nœud avec une valeur maximale dans son sous-arbre gauche
Notez que le nœud avec une valeur minimale (ou maximale) n'a pas d'enfant à gauche (ou à droite) et, par conséquent, sa suppression peut entraîner dans le premier ou le deuxième cas uniquement.
template <class T> void ABR <T> :: supprimer (Noeud <T>* ptr, Noeud <T>* parent){ if (ptr->gauche == 0 && ptr->droit == 0) { cout << ptr->donnees << parent->donnees<< endl; if (ptr != racine) { if (parent->gauche == ptr) parent->gauche = NULL; else parent->droit = NULL; } else racine = NULL; delete ptr; } else if (ptr->gauche && ptr->droit) { Noeud <T>* pere = ptr; // ici vous pouvez utiliser le prédécesseur aussi Noeud <T>* succ = successeur(ptr->droit, pere); int val = succ->donnees; supprimer(succ, pere); ptr->donnees = val; } else { Noeud <T>* enfant = (ptr->gauche)? ptr->gauche: ptr->droit; if (ptr != racine) { if (ptr == parent->gauche) parent->gauche = enfant; else parent->droit = enfant; } else racine = enfant; delete ptr; } }
Cette fonction prend deux paramètres : le nœud à supprimer et son parent (passé par référence)
Cette méthode est appelée par la méthode publique supprimer après avoir localisé le nœud
template <class T> void ABR <T> :: supprimer (const T& valeur) { Noeud <T>* parent = 0; Noeud <T>* del = recherche(valeur, racine, parent); if(del == 0){ cout << "Le noeud n'appartient pas a l'arbre" << endl; } else{ supprimer(del, parent); } }
Parcours infixe
// Fonction d'aide (Récursive) appeler par la fonction infixe template <class T> void ABR <T> :: infixe (Noeud <T>* ptr) const { if (!ptr){return;} infixe (ptr -> gauche); cout << ptr -> donnees << '\t'; infixe (ptr -> droit); }
Parcours préfixe
// Fonction d'aide (Récursive) appeler par la fonction prefixe template <class T> void ABR <T> :: prefixe (Noeud <T>* ptr) const { if (!ptr){return;} cout << ptr -> donnees << '\t'; prefixe (ptr -> gauche); prefixe (ptr -> droit); }
Parcours postfixe
// Fonction d'aide (Récursive) appeler par la fonction postfixe template <class T> void ABR <T> :: postfixe (Noeud <T>* ptr) const { if (!ptr){return;} postfixe (ptr -> gauche); postfixe (ptr -> droit); cout << ptr -> donnees << '\t'; }
Fichiers sources
#ifndef ABR_H #define ABR_H #include <iostream> using namespace std; // Définition du noeud en tant que struct template struct Noeud { T donnees; Noeud <T>* gauche; Noeud <T>* droit; }; // Définition de la classe Liste template <class T> class ABR { private: Noeud <T>* racine; int compteur; Noeud <T>* CreerNoeud (const T& valeur); void detruire (Noeud <T>* ptr); // Fonction d'aide void inserer (const T& value, Noeud <T>*& ptr); // Fonction d'aide void infixe (Noeud <T>* ptr) const; // Fonction d'aide void prefixe (Noeud <T>* ptr) const; // Fonction d'aide void postfixe (Noeud <T>* ptr) const; // Fonction d'aide Noeud <T>* successeur (Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide Noeud <T>* predecesseur (Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide void supprimer (Noeud <T>* ptr, Noeud <T>* parent); // Fonction d'aide Noeud <T>* recherche (const T& value, Noeud <T>* ptr, Noeud <T>*& parent) const; // Fonction d'aide public: ABR (); ~ABR (); void inserer (const T& value); void detruire (); void supprimer (const T& value); Noeud <T>* recherche (const T& value) const; void infixe () const; void prefixe () const; void postfixe () const; int taille () const; bool estVide () const; }; #endif
#ifndef ABR_CPP #define ABR_CPP #include "abr.h" // Constructeur template <class T> ABR <T> :: ABR():racine (0), compteur (0){} // Destructeur template <class T> ABR <T> :: ~ABR () { detruire(racine); } template <class T> Noeud <T>* ABR <T> :: CreerNoeud (const T& valeur){ Noeud <T>* temp = new Noeud <T>; temp -> donnees = valeur; temp -> gauche = NULL; temp -> droit = NULL; return temp; } // Inserer un noeud template <class T> void ABR <T> :: inserer (const T& valeur) { inserer (valeur, racine); compteur++; } // Rechercher un noeud template <class T> Noeud <T>* ABR <T> :: recherche (const T& valeur) const { Noeud <T>* parent = 0; return recherche (valeur, racine); } // Parcours infixe template <class T> void ABR <T> :: infixe () const { infixe(racine); } // Parcours prefixe template <class T> void ABR <T> :: prefixe () const { prefixe(racine); } // Parcours postfixe template <class T> void ABR <T> :: postfixe () const { postfixe(racine); } // Nombre de noeud dans l'arbre template <class T> int ABR <T> :: taille () const { return compteur; } template <class T> bool ABR <T> :: estVide () const { return (compteur == 0); } // La fonction d'aide (Récursive) appelée par le destructeur template <class T> void ABR <T> :: detruire (Noeud <T>* ptr) { if (!ptr){return;} detruire (ptr -> gauche); // détruire le sous-arbre gauche detruire (ptr -> droit); // détruire le sous-arbre droit delete ptr; // détruire la racine } // LA fonction d'aide (Récursive) appelée par la fonction membre inserer template <class T> void ABR <T> :: inserer (const T& valeur, Noeud <T>*& ptr) { // si l'arbre vide, inserer comme racine if (!ptr){ ptr = CreerNoeud (valeur); return; } // si la valeur est inférieure à la valeur de racine, // insérer le noeud dans le sous-arber gauche else if (valeur < ptr -> donnees){ inserer (valeur, ptr -> gauche); } // Sinon, insérer le noeud dans le sous-arber droit else{ inserer (valeur, ptr -> droit); } } // Fonction d'aide (Récursive) appeler par la fonction infixe template <class T> void ABR <T> :: infixe (Noeud <T>* ptr) const { if (!ptr){return;} infixe (ptr -> gauche); cout << ptr -> donnees << '\t'; infixe (ptr -> droit); } // Fonction d'aide (Récursive) appeler par la fonction prefixe template <class T> void ABR <T> :: prefixe (Noeud <T>* ptr) const { if (!ptr){return;} cout << ptr -> donnees << '\t'; prefixe (ptr -> gauche); prefixe (ptr -> droit); } // Fonction d'aide (Récursive) appeler par la fonction postfixe template <class T> void ABR <T> :: postfixe (Noeud <T>* ptr) const { if (!ptr){return;} postfixe (ptr -> gauche); postfixe (ptr -> droit); cout << ptr -> donnees << '\t'; } // Fonction d'aide (Récursive) appeler par la fonction membre recherche template <class T> Noeud <T>* ABR <T> :: recherche (const T& valeur, Noeud <T>* ptr, Noeud <T>*& parent) const { if (!ptr){ //Arbre est vide return NULL; } else if ((ptr->donnees) == valeur){ // la valeur recherchée est stockée dans la racine return ptr; } else if (valeur < (ptr->donnees)){ parent=ptr; // la valeur recherchée est dans le sous-arbre gauche return recherche (valeur, ptr->gauche, parent); } else{ parent=ptr; // sinon, la valeur recherchée est dans le sous-arbre droit return recherche (valeur, ptr->droit, parent); } } template <class T> Noeud <T>* ABR <T> :: successeur (Noeud <T>* ptr, Noeud <T>*& parent) const{ if (!ptr){return NULL;} Noeud <T>* courant = ptr; while (courant->gauche != 0){ parent = courant; courant = courant -> gauche; } return courant; } template <class T> Noeud <T>* ABR <T> :: predecesseur (Noeud <T>* ptr, Noeud <T>*& parent) const{ if (!ptr){return NULL;} Noeud <T>* courant = ptr; while (courant->droit != 0){ parent = courant; courant = courant -> droit; } return courant; } template <class T> void ABR <T> :: supprimer (const T& valeur) { Noeud <T>* parent = 0; Noeud <T>* del = recherche(valeur, racine, parent); if(del == 0){ cout << "Le noeud n'appartient pas a l'arbre" << endl; } else{ supprimer(del, parent); } } // Fonction d'aide (Récursive) appeler par la fonction membre supprimer template <class T> void ABR <T> :: supprimer (Noeud <T>* ptr, Noeud <T>* parent){ if (ptr->gauche == 0 && ptr->droit == 0) { cout << ptr->donnees << parent->donnees<< endl; if (ptr != racine) { if (parent->gauche == ptr) parent->gauche = NULL; else parent->droit = NULL; } else racine = NULL; delete ptr; } else if (ptr->gauche && ptr->droit) { Noeud <T>* pere = ptr; // ici vous pouvez utiliser le prédécesseur aussi Noeud <T>* succ = successeur(ptr->droit, pere); int val = succ->donnees; supprimer(succ, pere); ptr->donnees = val; } else { Noeud <T>* enfant = (ptr->gauche)? ptr->gauche: ptr->droit; if (ptr != racine) { if (ptr == parent->gauche) parent->gauche = enfant; else parent->droit = enfant; } else racine = enfant; delete ptr; } } #endif
Programme principal
#include "abr.cpp" int main ( ){ // Instanciation d'un ABR ABR <int> arbre; arbre.inserer(40); arbre.inserer(50); arbre.inserer(14); arbre.inserer(16); arbre.inserer(5); arbre.inserer(3); arbre.inserer(7); arbre.inserer(55); arbre.inserer(45); cout << '\n'; cout << "Le parcours infixe de cet arbre est : "<< endl; arbre.infixe(); cout << '\n'; cout << '\n'; cout << "Le parcours postfixe de cet arbre est : "<< endl; arbre.postfixe(); cout << '\n'; cout << '\n'; cout << "Le parcours prefixe de cet arbre est : "<< endl; arbre.prefixe(); cout << '\n'; cout << '\n'; if(arbre.recherche(3) != 0){ cout << "Le noeud avec la cle 3 appartient a l'arbre" << endl; } else{ cout << "Le noeud avec la cle 3 n'appartient pas a l'arbre" << endl; } if(arbre.recherche(60) != 0){ cout << "Le noeud avec la cle 60 appartient a l'arbre" << endl; } else{ cout << "Le noeud avec la cle 60 n'appartient pas a l'arbre" << endl; } arbre.supprimer(3); cout << '\n'; cout << "Le parcours infixe de l'arbre apres la suppression de 3 devient : "<< endl; arbre.infixe(); arbre.supprimer(40); cout << '\n'; cout << "Le parcours infixe de l'arbre apres la suppression 40 devient : "<< endl; arbre.infixe(); return 0; }
Résultat
Le parcours infixe de cet arbre est : 3 5 7 14 16 40 45 50 55 Le parcours postfixe de cet arbre est : 3 7 5 16 14 45 55 50 40 Le parcours prefixe de cet arbre est : 40 14 5 3 7 16 50 45 55 Le noeud avec la cle 3 appartient a l'arbre Le noeud avec la cle 60 n'appartient pas a l'arbre Le parcours infixe de l'arbre apres la suppression de 3 devient : 5 7 14 16 40 45 50 55 Le parcours infixe de l'arbre apres la suppression 40 devient : 5 7 14 16 45 50 55