Parcours infixe et tri

def tri_par_abr(liste):
    racine = None
    for v in liste:
        racine = inserer(racine, v)   # fonction inserer vue plus haut
    resultat = []
    infixe(racine, resultat)          # fonction infixe vue plus haut
    return resultat

# tri_par_abr([5, 2, 8, 1, 9, 3]) renvoie [1, 2, 3, 5, 8, 9]

Le parcours infixe d'un ABR renvoyant les valeurs triées, la liste finale est ordonnée. Le coût total est $O(n\log n)$ en moyenne, mais peut atteindre $O(n^2)$ si l'arbre devient dégénéré (par exemple si la liste est déjà triée).