Itérer sur un ABR

Itérer sur un ABR, c'est être capable d'écrire une boucle qui parcourt tous les éléments de l'arbre dans l'ordre

En python, pour un arbre de racine R, on voudrait avoir

   for n in R: print(n)

En C++, pour parcourir un std::set S, on peut écrire

   for(auto it = S.begin(); it != S.end(); ++it) cout << *it;

En python

Commençons par noter que dans certains langages - dont python - savoir parcourir suffit à savoir itérer.

Pour rendre itérable par ordre croissant les noeuds de l'arbre, il suffit d'écrire un parcours symétrique en utilisant le mot clé yield.

class Noeud:
    def __init__(self,val):
        self.clef = val; self.gauche = None; self.droite = None
    def __str__(self):
        return "{}".format(self.clef)
    
    def __iter__(self):
        if self.gauche:
            yield from self.gauche
        yield self
        if self.droite:
            yield from self.droite

h.afficher_arbre_binaire(R)

La méthode __iter__ de la classe Noeud nous permet d'écrire

for n in R: print(n, end = " ")

1 2 3 4 5 6 7 

Cette approche se base sur les coroutines, i.e. des fonctions dont l'exécution peut être suspendue et reprise.

Ce n'est pas actuellement disponible en C++ standard, mais

• proposé, mais pas encore approuvé, pour C++20

• disponible dans MSVC 2017 et clang 5.0, dans le namespace std::experimental

Element suivant

En l'absence de coroutine, il nous faut pouvoir écrire une fonction

def noeud_suivant(n):
    return # le noeud suivant dans l'ordre croissant

qui soit capable de se déplacer dans l'arbre indépendemment de lui, éventuellement sans en connaître la racine.

h.afficher_arbre_binaire(R)

• Les noeuds suivants de 2, 4, et 5 sont le minimum de leur sous-arbre droit. il suffira d'appeler notre fonction noeud_min pour y accéder

• Les noeuds suivants de 1 ,3, et 6 sont parmi leurs ancêtres. Plus exactement, ils sont le premier ancêtre pour lequel on remonte depuis l'enfant gauche.

• Le noeud suivant de 7 est None

La méthode la plus simple pour accéder aux ancêtres est d'ajouter un pointeur vers le noeud parent à chaque noeud. C'est la technique utilisée par la STL en C++.

class Noeud:
    def __init__(self,val,parent):
        self.clef = val
        self.parent = parent
        self.gauche = None 
        self.droite = None
    def __str__(self): 
        return "{}".format(self.clef)

def clef(R): return R.clef if R else "⌀"

def afficher_liens(R):
    return "[{}] P{} G{} D{}".format(clef(R),
           clef(R.parent), clef(R.gauche), clef(R.droite))

Noeud.__str__ = afficher_liens

h.afficher_arbre_binaire(R)

Le noeud suivant est donc

• le minimum du sous-arbre droit s'il existe
• sinon, le premier ancêtre dont on remonte depuis la gauche
• sinon, None s'il n'y a plus de parent en remontant.

def noeud_min(R):     
    return noeud_min(R.gauche) if R.gauche else R

def noeud_suivant(n):
    if n.droite:
        return noeud_min(n.droite)
    else:
        while n.parent and n.parent.gauche != n:
            n = n.parent
        return n.parent

Ces fonctions nous permettent d'itérer sur l'arbre par ordre croissant à partir du premier noeud (noeud_min(R))

n = noeud_min(R)
while n:
    print(n.clef, end=" ")
    n = noeud_suivant(n)

1 2 3 4 5 6 7 

Sans lien vers le parent

Il est aussi possible de trouver le noeud suivant sans avoir d'attribut parent à chaque noeud. Mais cela requiert

• de connaitre la racine de l'arbre

• quand le noeud courrant n'a pas d'enfant droit
  • de chercher le noeud courrant
  • en se souvenant du dernier noeud pour lequel on a tourné à gauche en cherchant

def noeud_suivant(R,n):
    if n.droite:
        return noeud_min(n.droite)
    else:
        suivant = None
        r = R
        while r.clef != n.clef:
            if n.clef < r.clef:
                suivant = r
                r = r.gauche
            else:
                r = r.droite
        return suivant

Cet algorithme fonctionne aussi, mais avec une complexité temporelle plus élevée (logarithmique au lieu de constant en temps amorti)

n = noeud_min(R)
while n:
    print(n.clef, end=" ")
    n = noeud_suivant(R,n)

1 2 3 4 5 6 7 

ASD1 Notebooks on GitHub.io © Olivier Cuisenaire, 2018