Insertion d’un élément dans un ABR

On voit ici comment insérer un élément {x} dans un ABR {\mathcal{A}(}de telle façon que l’arbre obtenu {\mathcal{A}^{\prime }} soit encore un ABR).

Il y a deux méthodes : « ajout aux feuilles » {(x} est inséré de façon à être une feuille de {\mathcal{A}^{\prime })} et « ajout à la racine » {(x} est inséré de façon à se retrouver à la racine de {\mathcal{A}^{\prime }).}

11.2.1 Insertion aux feuilles

On rappelle la fonction feuille, toujours utile :

La fonction addabr_f ajoute un élément {x} en tant que feuille sur un ABR {\mathcal{A}:} si {\mathcal{A}} est vide on le remplace par une feuille étiquetée {x,} sinon on compare {x} avec la racine {e} de {\mathcal{A}} et suivant le résultat on poursuit récursivement en insérant {x} soit dans le fils droit de {\mathcal{A}(}si {x>e)} soit dans le fils gauche (si {x\le e):}

Exemple : on part de l’arbre de recherche {T} décrit ci-dessous :

On évalue successivement :

Voici une représentation des arbres obtenus :

Figure du chapitre 11, page 3

Les fonctions list_of_abr et abr_of_list effectuent la conversion entre un ABR et la liste de ses étiquettes. Pour la fonction list_of_abr, on part de l’arbre vide et on ajoute les éléments de la liste avec addabr_f (la tête de la liste est ajoutée en dernier). Pour la fonction abr_of_list, la liste obtenue montre les étiquettes triées dans l’ordre croissant :

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :