INFORMATIQUE  LA RECHERCHE

Problème de la recherche

Introduction

Considérons un ensemble de grande taille ayant des caractéristiques communes. On veut faire de manière optimisée des opérations de recherche, d’adjonction et de suppression. à chaque élément, on associe une clé simple (critère unique) : recherche associative. Les bases de données traitent des critères plus généraux et des clés multiples.

Signature

sorte ensemble

utilise élément, clef

opérations

                clé : élément à clef

                vide : à ensemble

                ajouter : élément x ensemble à ensemble

                supprimer : clef x ensemble à ensemble

                 : clef x ensemble à booléen

Remarques :

-          Si plusieurs éléments ont la même clé, la recherche fournit une solution quelconque parmi les possibilités ; s’il n’y a pas de solutions (échec), on fournit une valeur spéciale.

-          La suppression commence par une recherche, en cas d’échec de la recherche, la suppression laisse l’ensemble inchangé.

-          En général, et s’il n’y a pas ambiguïté, on confond l’élément et sa clé.

La complexité fondamentale est celle de la comparaison entre deux clés. Si l’ensemble des clés est muni d’une relation d’ordre, on peut les trier avec des algorithmes efficaces. On distingue les méthodes de recherche séquentielle, les méthodes de recherche dichotomique, de hachage, et les méthodes arborescentes.

Arbres binaires de recherche

On représente un ensemble ordonné à n éléments par un arbre binaire à n nœuds (les nœuds sont les éléments), et c’est la comparaison avec la valeur d’un nœud qui va orienter la suite de la recherche.

Un arbre binaire de recherche est un arbre binaire tel que pour tout nœud x , les nœuds de son sous arbre-gauche s’ils en existent ont des valeurs inférieures ou égales à celle de x, et les nœuds de son sous arbre-droit des valeurs strictement supérieures ;

ce que l’on traduit par g(A) £  racine(A) < d(A).

 On obtient toujours l’ensemble ordonné par un parcours récursif gauche symétrique. Il n’y a pas unicité de la représentation.

Recherche d’un éléments

rechercher : valeur ´ arbre à booléen

 On compare l’élément à la valeur de la racine :

         égalité à succès

x = r é rechercher (x , < r , g  , d > ) = vraie

 -si le sous-arbre sélectionné est vide, l’élément est absent à échec

rechercher ( x ,  ) = faux

 - si la valeur est plus petite, on recommence récursivement dans le sous arbre gauche ; et réciproquement si la valeur est plus grande dans le sous arbre droit

        x < r é rechercher (x , < r , g  , d > ) = rechercher (x ,  g  )

x > r é rechercher (x , < r , g  , d > ) = rechercher (x ,  d  )

 Complexité : La complexité au pire est en O ( hauteur de l’arbre ).

Adjonction d’un élément aux feuilles

 ajout_feuille : arbre ´ valeur à arbre

 L’adjonction aux feuilles d’un élément se réalise en deux étapes :

-          étape de recherche pour savoir où insérer le nouvel élément ;

-          adjonction elle-même.

 On compare la valeur de l’élément à ajouter à celle de la racine pour déterminer si on l’ajoute sur le sous-arbre gauche ou droit.

                x r é ajout_feuille ( < r , g , d > , x ) = < r , ajout_feuille ( g , x ) , d >

                x > r é ajout_feuille ( < r , g , d > , x ) = < r , g , ajout_feuille ( d , x ) >

 Le dernier appel récursif se fait sur un arbre vide ; on crée un nouveau nœud à cette place pour le nouvel élément qui devient donc une feuille.

 ajout_feuille (  , x ) = < x ,  ,  >

 On peut construire un arbre binaire de recherche par adjonctions successives aux feuilles.

 On donne l’algorithme d’adjonction aux feuilles (récursif) en LDA :

               Fonction adjonction_feuille (A : arbre , e : entier ) : arbre

                début

                si est_vide(A)

                                alors retourner < e ,  ,  >

                sinon si ( e  racine(A) )

                                 retourner < racine(A) , ajout_feuille( g(A) , e ) , d(A) >

                sinon

                                 retourner < racine(A) ,g(A) ,  ajout_feuille( d(A) , e ) >

                fin

 On donne également une version itérative de l’algorithme (à voire td…).

 La complexité d’un adjonction est O ( hauteur de l’arbre ).

Adjonction d’un élément à la racine

Soit A un arbre binaire de recherche, on veut ajouter x à la racine.

 On procède en deux étapes :

-on coupe  A en deux arbres binaires de recherche G et D contenant respectivement tous les éléments £  x et tous ceux > x.

-construire l’arbre < x , G , D >

 à voire cours…

Suppression d’un élément

      supprimer : arbre ´ valeur à arbre

- recherche de l’élément à supprimer

-    suppression qui dépend de la place de l’élément, selon que le nœud est sans fils, avec un seul fils, ou avec deux fils. La suppression d’un nœud sans fils est immédiate. Pour la suppression un nœud avec un seul fils, on remplace ce nœud par son fils. Pour un nœud, avec deux fils, on dispose de deux solutions : soit on remplace le nœud à supprimer par le plus grand élément de son sous-arbre gauche, soit on le remplace par le plus petit élément de son sous-arbre droit.

 On donne l’algorithme de suppression en LDA :

               Fonction suppression ( A : arbre , e : entier ) : arbre

                début

       recherche de l’élément à supprimer

                si est_vide(A)

alors retourner erreur

                si ( e < racine(A) )

                                alors retourner < racine(A), suppression( g(A) , e ) , d(A) )

                sinon si ( e > racine(A) )

                                retourner < racine(A), g(A) , suppression( d(A) , e ) )

             suppression

                sinon

                                si est_feuille(A)

                                                alors retourner

                                sinon si est_vide(g(A))

                                                retourner d(A)

                                sinon si est_vide(d(A))

                                                retourner g(A)

                                sinon

on ajoute l’élément le plus à droite du sous-arbre gauche

                                                retourner < max_noeud(g(A)) , retire_max(g(A)), d(A) >

                fin

                Fonction max_noeud ( A : arbre ) : entier

          retourne le plus grand élément de l’arbre A, le plus à droite

                début

                si est_vide(d(A))

                                alors retourner racine(A)

                sinon

                                retourner max(d(A))          

                fin

                Fonction retire_max ( A : arbre ) : arbre

            retourne l’arbre privé de son plus grand élément

                début

                si est_vide(d(A))

                                alors retourner g(A)

                sinon

                                retourner < racine(A) , g(A) , retire_ max(d(A)) >

                fin

 La complexité est O ( hauteur de l’arbre ).

Conclusion, Tri par arbre binaire de recherche

Toutes les opérations ont une complexité dépendant de la hauteur de l’arbre binaire de recherche.  Elle varie entre O (log n ) pour des arbres équilibrés et O ( n ) pour des arbres dégénérés.

 Par conséquent, le tri par arbre binaire de recherche, obtenu par un parcours symétrique de l’arbre, a une complexité en comparaison dans le pire des cas variant entre O ( n log n ) et O ( n² ).