3-05. Algorithmes sur les arbres binaires
Dans ce chapitre, on va voir quelques algorithmes propres aux arbres. La bonne nouvelle, c’est qu’ils ressemblent beaucoup aux algos des graphes.😊
Notations
Soit T un arbre et x un nœud :
T.racine: nœud racinex.gauche: sous-arbre gauchex.droit: sous-arbre droitx.cle: clé (valeur)
Si x est une feuille, ses sous-arbres sont vide (NIL)
Implémentation des arbres binaires en Python
Pour utiliser des arbres binaires en Python, on va utiliser la classe BinaryTree ci-dessous. Cette implémentation s’appuie sur la nature récursive des arbres binaires.
class BinaryTree:
def __init__(self, value):
if not self.is_valid_node_value(value):
raise ValueError("value must be int or str")
self.value = value
self.left = None
self.right = None
def is_valid_node_value(self, value):
return True if isinstance(value, (str, int)) else False
def value_2_tree(self, value):
if isinstance(value, BinaryTree): return value
return BinaryTree(value)
def set_right(self, value):
new_node = self.value_2_tree(value)
self.right = new_node
def set_left(self, value):
new_node = self.value_2_tree(value)
self.left = new_node
def __str__(self, level=0, prefix=""):
result = ""
indent = " "
# Appel récursif sur le sous-arbre droit
if self.right: result += self.right.__str__(level + 1, "┌")
result += indent * max(level-1, 0)
if prefix: result += prefix + "─"
result += str(self.value) + "\n"
# Appel récursif sur le sous-arbre gauche
if self.left: result += self.left.__str__(level + 1, "└")
return result
La fonction __str__ affiche l’arbre via la commande print. Inutile de trop vous creuser la tête dessus, elle n’est pas au programme et est juste là par commodité.
Par contre, vous devez essayer de comprendre comment cette classe permet de construire un arbre binaire. On implémentera plus tard d’autres méthodes dans cette classe.
Prise en main de la classe BinaryTree
BinaryTree1. Créer un arbre binaire tree de racine A, avec A.gauche = B et A.droite = C.
2. Que renvoie la commande print(tree.left.right) ? Pourquoi ?
3. Comment créer un arbre tree2 de racine Z, avec Z.gauche = Y et Z.droit = tree ?
4. Que se passe-t-il si on essaie de créer un nœud dont la clé serait une liste ?
5. Comment changer la valeur d’un nœud ? Peut-on affecter une liste à la valeur d’un nœud ?
6. On souhaite limiter les valeurs affectables à un nœud à une chaîne de caractères ou un entier. Écrire la méthode set_value qui va permettre de faire cela.
Correction
1. Création de l’arbre binaire tree
tree = BinaryTree("A")
tree.set_left("B")
tree.set_right("C")
2. Elle renvoie None car tree.left est le nœud de valeur B et il n’a pas de fils.
3. Création de l’arbre binaire tree2
tree2 = BinaryTree("Z")
tree2.set_left("Y")
tree2.set_right(tree)
4. Les méthodes set_right et set_left créent un nouvel objet BinaryTree. Lors de l’instanciation, la méthode is_valid_node_value empêche d’attribue une valeur qui ne soit pas un entier ou une chaîne de caractères. Si on passe une liste comme valeur, le script va lever une exception ValueError.
5. Pour changer la valeur d’un nœud, il suffit de faire, par exemple :
tree.left.value = "K"
Aucune vérification n’est faite lors de ce changement de valeur. On pourrait donc passer une liste comme valeur sans lever d’exception.
6. Méthode set_value.
def set_value(self, value):
if not self.is_valid_node_value(value): raise ValueError("value must be int or str")
self.value = value
Hauteur et taille d’un arbre
- Calculer la taille et la hauteur d’un arbre.
Calculer la hauteur d’un arbre
Soit un arbre T :
HAUTEUR(T) :
si T = NIL :
renvoyer 0
sinon :
x ← T.racine
renvoyer 1 + max(HAUTEUR(x.gauche), HAUTEUR(x.droit))
Cet algorithme est récursif. C’est souvent le cas dans les algorithmes qui s’appliquent aux arbres.
Méthode « hauteur »
En vous basant sur l’implémentation Python proposée en début du chapitre, proposer une implémentation de la méthode get_height qui renvoie la hauteur de l’arbre (ou du sous-arbre) sur lequel elle est exécutée.
Correction
def get_height(self):
left_height = 0 if self.left is None else self.left.get_height()
right_height = 0 if self.right is None else self.right.get_height()
return max(left_height, right_height)+1
Calculer la taille d'un arbre
Soit un arbre T :
TAILLE(T) :
si T = NIL :
renvoyer 0
sinon :
x ← T.racine
renvoyer 1 + TAILLE(x.gauche) + TAILLE(x.droit)
Méthode « taille »
En vous basant sur l’implémentation Python proposée en début du chapitre, proposer une implémentation de la méthode get_size qui renvoie la hauteur de l’arbre (ou du sous-arbre) sur lequel elle est exécutée.
Correction
def get_size(self):
left_size = 0 if self.left is None else self.left.get_size()
right_size = 0 if self.right is None else self.right.get_size()
return 1 + left_size + right_size
Parcours en largeur
- Parcourir un arbre de différentes façons (ordre en largeur d’abord).
Le parcours en largeur d’un arbre suit le même principe que le parcours en largeur d’un graphe. Il consiste à explorer, à partir de sa racine, tous les nœuds d’un même niveau, puis tous les nœuds du niveau suivant, et ainsi de suite jusqu’à ce que tous les nœuds de l’arbre soient découverts.
Voici l’algo formel de parcours en largeur d’un arbre.
ParcoursLargeur(arbre T) :
F ← []
F.enfiler(T.racine)
tant que F n’est pas vide :
| x ← defiler(f)
| si x.gauche ≠ NIL :
| | F.enfiler(x.gauche.racine)
| si x.droit ≠ NIL :
| | F.enfiler(x.droit.racine)
Il est presque identique à celui d’un graphe. La principale différence est le fait qu’il est inutile de « marquer » un nœud car dans un arbre, il n’y a aucun cycle.
Parcours en largeur
Écrire la méthode get_bfs renvoyant la liste des nœuds obtenue lors d’un parcours en largeur.
Correction
def get_bfs(self):
result = []
queue = []
queue.append(self)
while len(queue) > 0 :
node = queue.pop(0)
result.append(node.value)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return result
Parcours en profondeur
- Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe).
Le parcours en profondeur tel que vu pour les graphes existe aussi pour les arbres. Il consiste à explorer tous ses nœuds en suivant les branches de l’arbre à partir de la racine et en commençant par la gauche (et donc en terminant par la droite), comme le montre la figure suivante
Mais le fait qu’il n’y ait pas de cycle dans un arbre permet d’avoir trois variantes de ce parcours en profondeur.
- préfixé : racine - gauche - droit – ABC
- infixé : gauche - racine - droit – BAC
- postfixé : gauche - droit - racine – BCA
Les trois algorithmes de parcours en profondeur d’un arbre binaire T sont écrits récursivement en utilisant la définition récursive de T.
fonction prefixe(T)
si T ≠ NIL:
traiter T.racine
prefixe(T.gauche)
prefixe(T.droit)
Parcours préfixé
fonction infixe(T)
si T ≠ NIL:
infixe(T.gauche)
traiter T.racine
infixe(T.droit)
Parcours infixé
fonction postfixe(T)
si T ≠ NIL:
postfixe(T.gauche)
postfixe(T.droit)
traiter T.racine
Parcours postfixé
Ces trois algorithmes sont en $*O(t)*$, où $*t*$ désigne la taille de l’arbre binaire.
L’instruction traiter peut désigner plusieurs instructions différentes : afficher, rechercher, etc.
Les trois parcours en profondeur
Proposez une implémentation des méthodes get_dfs_prefixe, get_dfs_infixe, get_dfs_postfixe renvoyant une liste des nœuds parcourus dans l’ordre souhaité.
Correction
def get_dfs_prefixe(self, search_result=None):
if search_result is None: search_result = []
search_result.append(self.value)
if self.left: self.left.get_dfs_prefixe(search_result)
if self.right: self.right.get_dfs_prefixe(search_result)
return search_result
def get_dfs_infixe(self, search_result=None):
if search_result is None: search_result = []
if self.left: self.left.get_dfs_infixe(search_result)
search_result.append(self.value)
if self.right: self.right.get_dfs_infixe(search_result)
return search_result
def get_dfs_postfixe(self, search_result=None):
if search_result is None: search_result = []
if self.left: self.left.get_dfs_postfixe(search_result)
if self.right: self.right.get_dfs_postfixe(search_result)
search_result.append(self.value)
return search_result
Arbres binaires de recherche
- Rechercher une clé dans un arbre de recherche, insérer une clé.
Rechercher une clé
Pour rechercher une clé particulière dans un ABR (arbre binaire de recherche), la méthode est extrêmement simple. Il suffit de parcourir l’arbre depuis la racine jusqu’à la clé (ou une feuille si la clé n’existe pas) en s’orientant à chaque nœud en fonction de la valeur de la clé :
- dans le sous-arbre gauche si
clé<nœud.clé; - dans le sous-arbre droit si
clé>nœud.clé.
fonction recherche(arbre T, valeur k) :
si T = NIL : renvoyer faux
x ← T.racine
si k = x.clé : renvoyer vrai
si k < x.clé : renvoyer recherche(x.gauche, k)
sinon : renvoyer recherche(x.droit, k)
La complexité de cet algorithme est en $*O(h)*$, où $*h*$ désigne la hauteur de l’ABR.
Insérer une clé
On ne va voir dans cette section que l’algorithme permettant d’insérer un nœud aux feuilles. L’insertion d’un nœud à la racine est plus complexe.
insertion(arbre T, clé y) :
x ← T.racine
tant que T ≠ NIL :
| x ← T.racine
| si y.clé < x.clé : T ← x.gauche
| sinon : T ← x.droit
si y.clé < x.clé : insérer y à gauche de x
sinon : insérer y à droite de x
Arbres binaires de recherche
Implémenter la classe BinarySearchTree qui aura les spécificités suivantes :
- la valeur d’un nœud ne peut être qu’un entier
- la méthode
add_leafajoutera une feuille à l’arbre au bon endroit, sachant qu’il s’agit d’un ABR - la méthode
contains_valuerenverraTruesi un nœud de l’arbre contient cette valeur,Falsesinon.
Vous pouvez utiliser la base ci-dessous :
class BinarySearchTree:
def __init__(self, value):
if not self.is_valid_node_value(value): raise ValueError("value must be int")
self.value = value
self.left = None
self.right = None
def is_valid_node_value(self, value):
return True if isinstance(value, int) else False
def __str__(self, level=0, prefix=""):
result = ""
indent = " "
# Appel récursif sur le sous-arbre droit
if self.right: result += self.right.__str__(level + 1, "┌")
result += indent * max(level-1, 0)
if prefix: result += prefix + "─"
result += str(self.value) + "\n"
# Appel récursif sur le sous-arbre gauche
if self.left: result += self.left.__str__(level + 1, "└")
return result
Correction
def add_leaf(self, value):
if not self.is_valid_node_value(value): raise ValueError("value must be int")
if value < self.value:
if self.left is None : self.left = self.value_2_tree(value)
else: self.left.add_leaf(value)
else:
if self.right is None : self.right = self.value_2_tree(value)
else: self.right.add_leaf(value)
def contains_value(self, value):
if not self.is_valid_node_value(value): raise ValueError("value must be int")
if value < self.value:
if self.left is None : return False
return self.left.contains_value(value)
elif value > self.value:
if self.right is None: return False
return self.right.contains_value(value)
else:
return True