Arbres binaires de recherche

Tri des clés

Pour obtenir la suite ordonnée de toutes les clés d’un ABR, il suffit de le parcourir l’arbre dans l’ordre infixe.

Exemple :

Recherche

Comme son nom l’indique, un ABR est spécifiquement adapté à la recherche d’enregistrements dont les clés sont données par les nœuds de l’arbre.

Exemple : recherche de la clé de valeur 6

Un ABR permet de rechercher rapidement (faible coût temporel).

Insertion

Pour insérer un nœud dans un arbre :

• on recherche le nœud dont la clé est la plus proche de celle du nœud à insérer
  (comme pour l’algorithme de recherche, sauf que le nœud recherché n’est pas sensé être trouvé),
• dès qu’une place est libre, on ajoute le nœud :
  • à gauche si sa clé est inférieure à celle de la feuille,
  • ou à droite dans le cas contraire.

Exemple : ajout d’un nœud dont la clé vaut 5 :

Dans le cas d’un ABR qui n’autorise pas les clés multiples, il faudra empêcher l’insertion d’un nœud dont la clé est déjà dans l’arbre.

Suppression

L’opération dépend du nombre de fils du nœud à supprimer.

Cas n°1 : le nœud à supprimer est une feuille

• On cherche le père du nœud à supprimer,
• On supprimer le lien père-fils.

Exemple : suppression du nœud 5

Cas n°2 : le nœud à supprimer a un unique fils

• On recherche le père du nœud à supprimer,
• On redirige le lien père-fils vers le fils (unique) du nœud à supprimer.

Exemple : suppression du nœud 6

Cas n°3 : le nœud à supprimer a deux fils

• On recherche le nœud de sa branche de gauche ayant la plus grande valeur,
  comme c’est le plus grand de cette branche, il n’a pas de fils droit (voir Plus grande valeur)
• On redirige son lien père-fils (comme dans le cas n°2 ! ),
• Et on remplace la valeur du nœud à supprimer par celle du nœud décroché.

Exemple : suppression du nœud 11

Exemple : suppression du nœud 7

Remarque : alternativement, on peut « décrocher » le nœud ayant la plus petite valeur de sa branche de droite.

Implémentation

On se propose d’implémenter l’interface présentée plus haut en langage Python.

Pour cela, on utilisera, comme des modules (sans les modifier !), les programmes suivant :

module arbre_b.py

from piles_files import File


######################################################################################
class Arbre_b:
    """ Arbre binaire
    """
    def __init__(self, racine = None):
        self.racine = racine # type : Noeud_b

    def __eq__(self, n):
        """ Permet d'utiliser le comparateur ==
            pour tester l'égalité entre deux arbres binaires
        """
        return self.racine == n.racine

    def __repr__(self):
        """ Affiche les valeurs des noeuds sous forme arborescente
        """
        lines = _build_tree_string(self.racine, 0, False, '-')[0]
        return '\n' + '\n'.join((line.rstrip() for line in lines))

    def list_infixe(self):
        """ Renvoie l'ensemble des valeurs des noeuds dans une liste
            selon l'ordre infixe
        """
        l = []
        if self.racine is not None:
            self.racine.list_infixe(l)
        return l

    def list_prefixe(self):
        l = []
        if self.racine is not None:
            self.racine.list_prefixe(l)
        return l

    def list_suffixe(self):
        l = []
        if self.racine is not None:
            self.racine.list_suffixe(l)
        return l

    def list_largeur(self):
        if self.racine is not None:
            return self.racine.list_largeur()

    def list_longueur(self):
        if self.racine is not None:
            return self.racine.list_longueur()

    def hauteur(self):
        if self.racine is not None:
            return self.racine.profondeur()

    def taille(self):
        if self.racine is not None:
            return self.racine.taille()

    def nbr_feuilles(self):
        if self.racine is not None:
            return self.racine.nbr_feuilles()

    def maxi(self):
        if self.racine is not None:
            return self.racine.maxi()

    def mini(self): 
        if self.racine is not None: 
            return self.racine.mini()

################################################################################
class Noeud_b:
    def __init__(self, v, g = None, d = None):
        self.g = g # fils gauche : type Noeud_b
        self.d = d # fils droit :  type Noeud_b
        self.v = v

    def __repr__(self):
        return str(self.v)

    def est_feuille(self):
        return self.g is None and self.d is None

    def __eq__(self, n):
        if n is None:
            return False
        return n.d == self.d and n.g == self.g # 2 appels récursifs !

    def profondeur(self):
        g = d = -1
        if self.g is not None:
            g = self.g.profondeur()
        if self.d is not None:
            d = self.d.profondeur()
        return 1 + max(g, d)

    def taille(self):
        g = d = 0
        if self.g is not None:
            g = self.g.taille()
        if self.d is not None:
            d = self.d.taille()
        return 1 + g + d

    def nbr_feuilles(self):
        if self.d is None and self.g is None:
            return 1
        else:
            g = d = 0
            if self.g is not None:
                g = self.g.nbr_feuilles()
            if self.d is not None:
                d = self.d.nbr_feuilles()
            return g + d

    def list_infixe(self, l):
        if self.g is not None:
            self.g.list_infixe(l)
        l.append(self.v)
        if self.d is not None:
            self.d.list_infixe(l)

    def list_prefixe(self, l):
        l.append(self.v)
        if self.g is not None:
            self.g.list_prefixe(l)
        if self.d is not None:
            self.d.list_prefixe(l)

    def list_suffixe(self, l):
        if self.g is not None:
            self.g.list_suffixe(l)
        if self.d is not None:
            self.d.list_suffixe(l)
        l.append(self.v)

    def list_largeur(self):
        l = []
        f = File()
        f.enfiler(self) # on place la racine dans la file
        while not f.est_vide():
            n = f.defiler()
            l.append(n.v)
            if n.g is not None:
                f.enfiler(n.g)
            if n.d is not None:
                f.enfiler(n.d)
        return l

    def list_longueur(self):
        l = []
        f = Pile()
        f.push(self) # on place la racine dans la file

        while not f.est_vide():
            n = f.pop()
            l.append(n.v)
            if n.g is not None:
                f.push(n.g)
            if n.d is not None:
                f.push(n.d)
        return l

    def maxi(self, m = None):
        if m is None or self.v > m:
            m = self.v
        if self.g is not None:
            m = max(m, self.g.maxi(m))
        if self.d is not None:
            m = max(m, self.d.maxi(m))
        return m

    def mini(self, m = None): 
        if m is None or self.v > m: 
            m = self.v 
        if self.g is not None: 
            m = min(m, self.g.mini(m)) 
        if self.d is not None: 
            m = min(m, self.d.mini(m)) 
        return m 



# Source : https://github.com/joowani/binarytree/blob/22fc4b72c3be23d08016a2c863e6268f8ad49068/binarytree/__init__.py#L160
def _build_tree_string(root, curr_index, index=False, delimiter='-'):
    """Recursively walk down the binary tree and build a pretty-print string.
    In each recursive call, a "box" of characters visually representing the
    current (sub)tree is constructed line by line. Each line is padded with
    whitespaces to ensure all lines in the box have the same length. Then the
    box, its width, and start-end positions of its root node value repr string
    (required for drawing branches) are sent up to the parent call. The parent
    call then combines its left and right sub-boxes to build a larger box etc.
    :param root: Root node of the binary tree.
    :type root: binarytree.Node
    :param curr_index: Level-order_ index of the current node (root node is 0).
    :type curr_index: int
    :param index: If set to True, include the level-order_ node indexes using
        the following format: ``{index}{delimiter}{value}`` (default: False).
    :type index: bool
    :param delimiter: Delimiter character between the node index and the node
        value (default: '-').
    :type delimiter:
    :return: Box of characters visually representing the current subtree, width
        of the box, and start-end positions of the repr string of the new root
        node value.
    :rtype: ([str], int, int, int)
    .. _Level-order:
        https://en.wikipedia.org/wiki/Tree_traversal#Breadth-first_search
    """
    if root is None:
        return [], 0, 0, 0

    line1 = []
    line2 = []
    if index:
        node_repr = '{}{}{}'.format(curr_index, delimiter, root.v)
    else:
        node_repr = str(root.v)

    new_root_width = gap_size = len(node_repr)

    # Get the left and right sub-boxes, their widths, and root repr positions
    l_box, l_box_width, l_root_start, l_root_end = \
        _build_tree_string(root.g, 2 * curr_index + 1, index, delimiter)
    r_box, r_box_width, r_root_start, r_root_end = \
        _build_tree_string(root.d, 2 * curr_index + 2, index, delimiter)

    # Draw the branch connecting the current root node to the left sub-box
    # Pad the line with whitespaces where necessary
    if l_box_width > 0:
        l_root = (l_root_start + l_root_end) // 2 + 1
        line1.append(' ' * (l_root + 1))
        line1.append('_' * (l_box_width - l_root))
        line2.append(' ' * l_root + '/')
        line2.append(' ' * (l_box_width - l_root))
        new_root_start = l_box_width + 1
        gap_size += 1
    else:
        new_root_start = 0

    # Draw the representation of the current root node
    line1.append(node_repr)
    line2.append(' ' * new_root_width)

    # Draw the branch connecting the current root node to the right sub-box
    # Pad the line with whitespaces where necessary
    if r_box_width > 0:
        r_root = (r_root_start + r_root_end) // 2
        line1.append('_' * r_root)
        line1.append(' ' * (r_box_width - r_root + 1))
        line2.append(' ' * r_root + '\\')
        line2.append(' ' * (r_box_width - r_root))
        gap_size += 1
    new_root_end = new_root_start + new_root_width - 1

    # Combine the left and right sub-boxes with the branches drawn above
    gap = ' ' * gap_size
    new_box = [''.join(line1), ''.join(line2)]
    for i in range(max(len(l_box), len(r_box))):
        l_line = l_box[i] if i < len(l_box) else ' ' * l_box_width
        r_line = r_box[i] if i < len(r_box) else ' ' * r_box_width
        new_box.append(l_line + gap + r_line)

    # Return the new box, its width and its root repr positions
    return new_box, len(new_box[0]), new_root_start, new_root_end



if __name__ == "__main__":
    a = Arbre_b(Noeud_b(4, Noeud_b(2, Noeud_b(8), Noeud_b(5)), Noeud_b(7, d = Noeud_b(9, Noeud_b(3), Noeud_b(1, Noeud_b(6))))))
    print(a)

    b = Arbre_b(Noeud_b(5, Noeud_b(10, d = Noeud_b(3)), Noeud_b(6, Noeud_b(1, Noeud_b(9), Noeud_b(4)), Noeud_b(12))))
    print(b)

module piles_files.py

#####################################################################
class Pile:
    def __init__(self):
        self.__p = []
        self.pop = self.depiler
        self.push = self.empiler
        self.is_empty = self.est_vide

    def __repr__(self):
        l = []
        p = Pile()
        m = 0
        while not self.est_vide():
            c = self.depiler()
            p.empiler(c)
            l.append(str(c))
            m = max(m, len(str(c)))
            
        while not p.est_vide():
            self.empiler(p.depiler())

        for i in range(len(l)):
            l[i] = "│" + l[i].ljust(m) +"│"
        
        return "\n".join(l) + "\n└"+ m*"─" + "┘"

    def est_vide(self):
        return len(self.__p) == 0

    def empiler(self, v):
        self.__p.append(v)

    def depiler(self):
        return self.__p.pop()


#####################################################################
class File:
    def __init__(self):
        self.__p = []
        self.dequeue = self.defiler
        self.enqueue = self.enfiler
        self.is_empty = self.est_vide

    def __repr__(self):
        l = []
        p = File()

        while not self.est_vide():
            c = self.defiler()
            p.enfiler(c)
            l.append(str(c))
            
        while not p.est_vide():
            self.enfiler(p.defiler())

        t = " ".join(l)
        
        return " "+len(t)*"─" +"\n"+ "→"+t +"\n "+ len(t)*"─"

    def est_vide(self):
        return len(self.__p) == 0

    def enfiler(self, v):
        self.__p.append(v)

    def defiler(self):
        return self.__p.pop(0)

#####################################################################
if __name__ == "__main__":
    p = File()
    p.enfiler("A")
    p.enfiler("B")
    p.enfiler("C")
    print(p)

class ABR(Arbre_b): 
    def __init__(self, racine = None): 
        super().__init__(racine)

• min() → Noeud_b
• max() → Noeud_b

def min(self):
    """ Renvoie la plus petite valeur de l'arbre """
    def m(n):
        if n.g is not None:
            return m(n.g)
        return n
    return m(self.racine)


def max(self):
    """ Renvoie la plus grande valeur de l'arbre """
    def m(n):
        if n.d is not None:
            return m(n.d)
        return n
    return m(self.racine)

def min(self):
    n = self.racine
    p = None
    while n is not None:
        p = n
        n = n.g
    return p

def max(self):
    n = self.racine
    p = None
    while n is not None:
        p = n
        n = n.d
    return p

• chercher(v) → Noeud_b

def chercher(self, v):
    """ Renvoie le Noeud de valeur v
        None si aucun noeud n'a cette valeur
    """
    n = self.racine
    while n is not None:
        if v > n.v:
            n = n.d
        elif v < n.v:
            n = n.g
        else:
            return n

• inserer(v)

def chercher_plus_proche(self, v):
    n = self.racine
    p = None
    while n is not None:
        if v < n.v:
            p = n
            n = n.g
        elif v > n.v:
            p = n
            n = n.d
        else:
            return
    return p

def inserer(self, v):
    """ Insère un nouveau Noeud de valeur v dans l'arbre
        (version itérative)
    """
    if self.racine is None:
        self.racine = Noeud_b(v)

    else:
        n = self.racine
        while n is not None:
            if v < n.v:
                if n.g is None:
                    n.g = Noeud_b(v)
                    return
                n = n.g

            elif v > n.v:
                if n.d is None:
                    n.d = Noeud_b(v)
                    return
                n = n.d

            else:
                return # clé déjà dans l'arbre

• supprimer(v)

def supprimer(self, v):
    """ Supprime le Noeud de valeur v dans l'arbre
        (s'il existe)
    """
    # On recherche le noeud n de valeur v
    # ... et son père p
    n = self.racine
    p = None  # Père de n
    while n is not None:
        if v > n.v:
            p = n
            n = n.d
        elif v < n.v:
            p = n
            n = n.g
        else:
            break
    if n is None:
         return
    
    if n.d is None and n.g is None:  # Feuille
        if n.v < p.v:
            p.g = None
        else:
            p.d = None
                
    elif n.d is None:                # Fils unique à gauche
        if p.v < n.v:
            p.g = n.d
        else:
            p.d = n.d
    elif n.g is None:                # Fils unique à droite
        if p.v < n.v: 
            p.d = n.d 
        else: 
            p.d = n.g        
        
    else:                            # 2 fils
        # on cherche le plus grand noeud à gauche (noeud à déplacer m) -> m
        #  ... et son père p
        m = n.g
        p = n
        while m.d is not None:
            p = m
            m = m.d
            
        # On supprime la référence du noeud à déplacer (lien père-fils)
        if m.v < p.v: # il est à gauche de son père p
            p.g = m.g
        else:         # il est à droite de son père p
            p.d = m.g

        # On remplace la valeur du noeud supprimer par celle du noeud à déplacer
        n.v = m.v

• verifier() → bool (méthode récursive, d’après la définition d’un ABR)

Sources :
https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche
http://pageperso.lif.univ-mrs.fr/~francois.denis/algoMPCI/chap1.pdf