Programme Officiel

Contenus

Capacités attendues

Commentaires

Algorithmes sur les arbres binaires et sur les arbres binaires de recherche.

Calculer la taille et la hauteur d’un arbre.

Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe ; ordre en largeur d’abord).

Rechercher une clé dans un arbre de recherche, insérer une clé.

Une structure de données récursive adaptée est utilisée.

L’exemple des arbres permet d’illustrer la programmation par classe.

La recherche dans un arbre de recherche équilibré est de coût logarithmique.

Lien vers le programme complet

Dans ce chapitre nous allons voir quelques algorithmes classiques sur les arbres:

  • Calcul de la taille et de la hauteur de l'arbre.
  • Parcours de l'arbre de différentes façons
  • Recherche et insertion d'une clé dans un arbre binaire de recherche.

Description de la structure de données

Pour représenter les arbres, nous allons décrire l'arbre à partir d'une classe Node récursive avec les attributs suivants:

  • value: valeur ou clé du nœud de type numérique,
  • left: sous-arbre gauche de type Node,
  • right: sous-arbre droit de type Node,

Cette structure de données est récursive car les attributes left et right de l'objet Node sont eux-mêmes de type Node.

 

La syntaxe utilisée est basée sur le package python binarytree ce qui à 'l'inconvénient d'être en anglais, mais qui nous permettra de programmer et tester facilement nos algorithmes en Python.


Entrée
from binarytree import Node, tree
# On peut facilement créer un arbre aléatoire
mon_arbre = tree(height=3)

# L'affichage de l'arbre est aisé
print("Arbre aléatoire")
print(mon_arbre)

# ou créer l'arbre de toutes pièces
arbre = Node(3)
arbre.left = Node(2)
arbre.left.left = Node(1)
arbre.left.right = Node(4)
arbre.right = Node(6)
print("A la main")
print(arbre)
Sortie
Arbre aléatoire

       ___12_______
      /            \
     11           __5___
    /  \         /      \
  _7    2      _6       _0
 /            /  \     /  \
10           14   4   13   3

A la main

    __3
   /   \
  2     6
 / \
1   4

Calculer la hauteur de l'arbre

Pour rappel:

Hauteur d'un arbre

La hauteur d'un arbre est la plus grande profondeur d'une feuille de l'arbre.

Pour rappel:

Taille d'un arbre

La taille d'un arbre est son nombre de nœuds.

Nous allons à nouveau utiliser une fonction recursive.

A chaque appel, on renvoie 1 + max(taille(node.left), taille(node.right)).

Mais comme toute fonction recursive, il faut un cas de base qui ne nécessite pas le rappel de la fonction(sans quoi on aurait une boucle infinie). Ce cas est l'absence de noeud, cela signifie que le noeud parent était une feuille, et renvoie -1 pour diminuer la hauteur accumulée de 1.


Entrée
def hauteur(node):
    """Fonction récursive renvoyant la hauteur d'un arbre
    
    Arguments
    ---------
    node: Node
        Le noeud racine de l'arbre
    
    Returns
    -------
    int
        La hauteur de l'arbre
    """
    # Cas de base 
    if not(node):
        return -1
    else:
        # print(node)
        return 1 + max(hauteur(node.left), hauteur(node.right))
        
hauteur(mon_arbre)
Résultat
3

N'hésitez pas à décommenter le print pour observer les arbres sur lesquels est appelé cette fonction.

Calculer la taille de l'arbre

Pour rappel:

Taille d'un arbre

La taille d'un arbre est son nombre de nœuds.

Encore une fois, nous allons utiliser une fonction recursive.

A chaque appel, au lieu d'utiliser le maximum comme précédemment on va simplement additionner les hauteurs des sous-arbres: on renvoie 1 + hauteur(node.left), hauteur(node.right)).

Le cas de base, en cas d'absence de noeud, on renvoie 0.


Entrée
def taille(node):
    """Fonction récursive renvoyant la taille d'un arbre
    
    Arguments
    ---------
    node: Node
        Le noeud racine de l'arbre
    
    Returns
    -------
    int
        La taille de l'arbre
    """
    # Cas de base 
    if not(node):
        return 0
    else:
        # print(node)
        return 1 + taille(node.left) + taille(node.right)
  
print(mon_arbre)
print("taille")
taille(mon_arbre)
Sortie
       ___12_______
      /            \
     11           __5___
    /  \         /      \
  _7    2      _6       _0
 /            /  \     /  \
10           14   4   13   3

taille

Résultat
12

Parcours de l'arbre

Nous allons voir quatre méthodes de parcours des arbres, en fonction de l'ordre dans lequel on parcourt les noeuds:

  • parcours préfixe
  • parcours postfixe
  • parcours infixe
  • parcours en largeur

Comparaisons des parcours d'arbres

Parcours préfixe

Dans cet ordre, chaque nœud est visité puis chacun de ses fils.

Voici le pseudo-code extrait de l'article Wikipedia sur les arbres.

visiterPréfixe(Arbre A) :
    visiter (A)
    Si nonVide (gauche(A))
          visiterPréfixe(gauche(A))
    Si nonVide (droite(A))
          visiterPréfixe(droite(A))

Parcours postfixe

On affiche chaque nœud après avoir affiché chacun de ses fils.

Voici le pseudo-code extrait de l'article Wikipedia sur les arbres.

visiterPostfixe(Arbre A) :
    Si nonVide(gauche(A))
       visiterPostfixe(gauche(A))
    Si nonVide(droite(A))
       visiterPostfixe(droite(A))
    visiter(A)

Parcours infixe

On visite chaque nœud entre les nœuds de son sous-arbre de gauche et les nœuds de son sous-arbre de droite. C'est une manière assez commune de parcourir un arbre binaire de recherche, car il donne les valeurs dans l'ordre croissant.

Voici le pseudo-code extrait de l'article Wikipedia sur les arbres.

visiterInfixe(Arbre A) :
    Si nonVide(gauche(A))
       visiterInfixe(gauche(A))
    visiter(A)
    Si nonVide(droite(A))
       visiterInfixe(droite(A))

Parcours en largeur

On parcours les bnoeuds de gaucha à droite étage par étage, comme si on "lisait" l'arbre.

Voici le pseudo-code issu de l'article Wikipedia sur les arbres.

Ce code n'est pas recusrif et a la particularité d'utiliser une structure de file avec les méthodes enfiler et défiler.

ParcoursLargeur(Arbre A) {
   f = FileVide
   enfiler(Racine(A), f)
   Tant que (f != FileVide) {
       nœud = defiler(f)
       Visiter(nœud)                        //On choisit de faire une opération
       Si (gauche(nœud) != null) Alors
           enfiler(gauche(nœud), f)
       Si (droite(nœud) != null) Alors
           enfiler(droite(nœud), f)
   }
}

Voici un exemple d'implémentation en Python utilisant une liste en guise de file avec les méthodes:

  • list.insert(0, el), pour enfiler l'élément à l'index 0.
  • list.pop(), pour supprimer et renvoyer le dernier élément de la file(le défiler).

Entrée
def parcours_largeur(arbre):
    f = []
    f.insert(0, arbre)
    while f:
        noeud = f.pop()
        print(noeud.value)
        if noeud.left:
            f.insert(0, noeud.left)
        if noeud.right:
            f.insert(0, noeud.right)

print(mon_arbre)
parcours_largeur(mon_arbre)
Sortie
       ___12_______
      /            \
     11           __5___
    /  \         /      \
  _7    2      _6       _0
 /            /  \     /  \
10           14   4   13   3

12
11
5
7
2
6
0
10
14
4
13
3

Arbre binaire de recherche

Comme nous l'avons vu dans le chapitre sur les arbres de la partie structure de données,

un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.

Pour rappel:

 

Il s'agit d'un arbre binaire dans lequel toutes les valeurs dans le sous-arbre gauche d'un nœud sont inférieures à la valeur à la racine de l'arbre et toutes les valeurs dans le sous-arbre droit d'un nœud sont supérieures ou égales à la valeur à la racine de l'arbre.

Nous allons voir les algorithmes permettant la recherche et l'insertion d'une clé.

Encore une fois nous utiliserons le package binarytree qui permet de facilementcréer des arbres binaires grâce à la fonction bst(binary search tree).


Entrée
from binarytree import bst
abr = bst(height=3)
print(abr)
Sortie
  ____8________
 /             \
0__         ____13
   \       /
    6     10
   /     /  \
  5     9    12

Insertion d'une clé

L'insertion d'un nœud commence par une recherche : on cherche la clé du nœud à insérer ; lorsqu'on arrive à une feuille, on ajoute le nœud comme fils de la feuille en comparant sa clé à celle de la feuille : si elle est inférieure, le nouveau nœud sera à gauche ; sinon il sera à droite.

fonction Insertion(A,e)
        Si A = .
            retourner (e,.,.)
        Sinon A = (x,FilsGauche,FilsDroit)
            Si e < x
                retourner (x,Insertion(FilsGauche,e),FilsDroit)
            Sinon
                retourner (x,FilsGauche,Insertion(FilsDroit,e))

ABR sur Wikipedia

On peut traduire cet algorithme en Python de cette façon:


Entrée
def insertion(node, e):
    """Insertion de l'élément e dans l'arbre node
    
    Arguments
    ---------
    node: binarytree.Node
        l'arbre dans lequel doit être inséré le noeud
    e: Number
        L'élément à insérer
    Returns
    -------
    binarytree.Node
        l'arbre modifié
    """
    if not(node):
        return Node(e)
    x = node.value
    if e < x:
        return Node(value=x,
                    left=insertion(node.left, e),
                    right=node.right)
    else:
        return Node(value=x,
                    left=node.left,
                    right=insertion(node.right, e))
print(abr)
print(insertion(abr, 4))
Sortie
  ____8________
 /             \
0__         ____13
   \       /
    6     10
   /     /  \
  5     9    12


  ______8________
 /               \
0____         ____13
     \       /
      6     10
     /     /  \
    5     9    12
   /
  4

Recherche d'une clé

Puisque ce type d'arbre est trié, nous pouvons utiliser une méthode de recherche dichotomique telle que nous l'avions vu en première.

On peut ainsi éliminer la moitié de l'arbre à chaque itération et la complexité est log(n)log(n) si l'arbre est équilibré.

Voici le pseudo code de cet algorithme.

fonction Recherche(A,e)

        Si A = .

            retourner Faux

        Sinon A = (x,FilsGauche,FilsDroit)

            Si x = e

                retourner Vrai

            Sinon si e < x

                retourner Recherche(FilsGauche,e)

            Sinon

                retourner Recherche(FilsDroit,e)

Implémenter cet algorithme en Python en utilisant le module binarysearchtree.