Algorithmes et Structures de Donnés 3

Etude de cas: 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ément

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écurcivement 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² ).