Tri arborescent python – Implémentation de l’algorithme

Le tri arborescent python d’arbre (Binary Search Tree) est un algorithme de tri comparatif qui utilise une structure d’arborescence de recherche binaire. Il équivaut au tri rapide, sa complexité moyenne est de Θ (n log n) en moyenne, mais Θ (n2) dans le pire des cas.

Cependant, il est moins efficace car il doit créer une structure de données complexe et le tri rapide est un tri sur place. Par conséquent, il n’est pas utilisé dans la pratique.

Référence : https://fr.wikipedia.org/wiki/Tri_arborescent

Tri arborescent code python

class NoeudArbreBinaire:
    def __init__(self, cle):
        self.cle = cle
        self.left = None
        self.right = None
        self.parent = None
 
    def inserer(self, noeud):
        if self.cle > noeud.cle:
            if self.left is None:
                self.left = noeud
                noeud.parent = self
            else:
                self.left.inserer(noeud)
        elif self.cle <= noeud.cle:
            if self.right is None:
                self.right = noeud
                noeud.parent = self
            else:
                self.right.inserer(noeud)
 
    def enOrdre(self):
        if self.left is not None:
            self.left.enOrdre()
        print(self.cle, end=' ')
        if self.right is not None:
            self.right.enOrdre()
 
 
class RechercheArbreBinaire:
    def __init__(self):
        self.root = None
 
    def enOrdre(self):
        if self.root is not None:
            self.root.enOrdre()
 
    def ajouter(self, cle):
        nouveau_noeud = NoeudArbreBinaire(cle)
        if self.root is None:
            self.root = nouveau_noeud
        else:
            self.root.inserer(nouveau_noeud)
 
 
rechercheBinaireArbre = RechercheArbreBinaire()
 
tableau = [11, 222, 3, 899, 24, 5, 46, 67]
print(tableau)

for x in alist:
    rechercheBinaireArbre.ajouter(x)
print('tableau trié:')
rechercheBinaireArbre.enOrdre()

Aussi vous pouvez consulter sur ce site : https://fr.wikipedia.org/wiki/Algorithme_de_tri


Tri arborescent python


https://128mots.com/index.php/category/python/

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *