Problème — Dictionnaire ordonné par ABR

On enrichit le nœud d'une valeur associée à la clé. La structure d'ABR sur les clés garantit que le parcours infixe les restitue triées.

class NoeudDico:
    def __init__(self, cle, valeur):
        self.cle = cle
        self.valeur = valeur
        self.gauche = None
        self.droit = None

class Dictionnaire:
    def __init__(self):
        self.racine = None

    def inserer(self, cle, valeur):
        self.racine = self._inserer(self.racine, cle, valeur)

    def _inserer(self, noeud, cle, valeur):
        if noeud is None:
            return NoeudDico(cle, valeur)
        if cle < noeud.cle:
            noeud.gauche = self._inserer(noeud.gauche, cle, valeur)
        elif cle > noeud.cle:
            noeud.droit = self._inserer(noeud.droit, cle, valeur)
        else:
            noeud.valeur = valeur     # mise a jour
        return noeud

    def rechercher(self, cle):
        noeud = self.racine
        while noeud is not None:
            if cle == noeud.cle:
                return noeud.valeur
            noeud = noeud.gauche if cle < noeud.cle else noeud.droit
        return None

    def cles_triees(self):
        acc = []
        self._infixe(self.racine, acc)
        return acc

    def _infixe(self, noeud, acc):
        if noeud is not None:
            self._infixe(noeud.gauche, acc)
            acc.append(noeud.cle)
            self._infixe(noeud.droit, acc)

d = Dictionnaire()
d.inserer(3, "trois")
d.inserer(1, "un")
d.inserer(2, "deux")
print(d.rechercher(2))   # deux
print(d.cles_triees())   # [1, 2, 3]

La recherche s'effectue en moyenne en $O(\log n)$ pour un arbre équilibré, contre $O(n)$ pour une liste non triée.