Théorie des graphes

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

Arbre binaire de recherche

Un arbre binaire de recherche est un arbre dans lequel chaque nœud est supérieur à son fils gauche et inférieur à son fils droit et il n’y a pas de nœuds égaux
Un arbre binaire de recherche est intéressant puisqu’il est toujours possible de connaître dans quelle branche de l’arbre se trouve un élément et de proche en proche le localiser dans l’arbre.

Les propriétés ci-dessus de l'arbre binaire de recherche permettent de classer les clés afin que les opérations telles que recherche, minimum et maximum puissent être effectuées rapidement. S'il n'y a pas d'ordre, il se peut que nous devions comparer chaque clé pour rechercher une clé donnée.

Rechercher un élément

Pour rechercher une clé donnée dans L'arbre binaire de recherche, nous la comparons d'abord avec racine, si la clé est présente à racine, nous retournons racine. Si la clé est supérieure à la clé de la racine, on recommence pour le sous-arbre droit du noeud racine. Sinon, le sous-arbre gauche.

                Algorithme rechercher(Noeud , cle)
                    Si (Noeud = Null) alors 
                        Retourne Faux
                    Sinon Si (Noeud.val = cle ) alors
                        Retourne Vrai
                    Sinon Si (cle < Noeud.val ) alors
                        Retourne rechercher(Noeud.gauche, cle) 
                    Sinon
                        Retourne rechercher(Noeud.droit, cle) 
                    Fin SI
                FIN
            
                class Noeud:
                    def __init__(self, cle):
                        self.gauche = None
                        self.droit = None
                        self.val = cle  
                
                    def rechercher(Noeud, cle): 
                        assert Noeud != None
                        id Noeud is None:
                            return False
                        elseif Noeud.val == cle:
                            return True
        
                        if Noeud.val < cle: 
                            return rechercher(Noeud.droit, cle) 
                        
                        return rechercher(Noeud.gauche, cle) 
            

Insertion d'un élément

Une nouvelle clé est toujours inséré dans la feuille. On commence à chercher une valeur à partir de la racine jusqu'à ce qu'on atteigne une feuille. Une fois qu'une feuille est trouvée, le nouveau nœud est ajouté en tant qu'enfant de la feuille.

                    Algorithme Inserer(Noeud , cle)
                        Si (Noeud = null) alors
                            « ajouter un nœud pour cle à cet endroit» 
                        
                        Si(val > Noeud.val)
                            Insérer (Noeud.droit, val) 
                        Sinon
                            Insérer (Noeud.gauche, val)
                        FINSI
                    FIN
            
                    class Noeud:
                        def __init__(self, key):
                            self.gauche = None
                            self.droit = None
                            self.val = key  
                    
                    def inserer(noeud,cle): 
                        if noeud is None: 
                            noeud = Noeud(val) 
                        else: 
                            if noeud.val < node.val: 
                                if noeud.droit is None: 
                                    noeud.droit = Noeud(cle) 
                                else: 
                                    inserer(noeud.droit, cle) 
                            else: 
                                if noeud.gauche is None: 
                                    noeud.gauche = Noeud(cle)  
                                else: 
                                    inserer(noeud.gauche, cle) 
                            
                

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :