Arbres binaires¶
Un arbre binaire est un arbre d’arité deux. On peut aussi dire qu'un arbre binaire est un arbre dont chaque nœud possède au plus deux fils.
Sous-arbres d'un arbre binaire¶
On différencie les deux sous-arbres : le sous-arbre gauche et sous-arbre droit.
Les deux sous arbres peuvent être vides.
Question
Quels sont les sous arbres du nœud O ?
Arbres binaires complets¶
On rencontre très souvent des arbres binaires dits complets parce qu'aucun des fils gauche ou droit n'est manquant.
Question
Quelle est la taille d'un arbre binaire complet de hauteur \(h\) ?
Encadrement de la hauteur d'un arbre binaire¶
Nous avons vu que la hauteur d'un arbre filiforme était de :
\(h\) = \(\tau\) - 1
De plus, nous pouvons déterminer (expliqué au tableau) que la hauteur d'un arbre binaire complet est :
\(h = \lfloor \log_2 \tau \rfloor\)
On en déduit donc que :
\(\lfloor \log_2 \tau \rfloor \leq h \leq \tau - 1\)
Encadrement de la taille d'un arbre binaire¶
Nous avons vu que la hauteur d'un arbre filiforme était de :
\(h\) = \(\tau\) - 1
On en déduit que :
\(\tau\) = \(h\) + 1
Soit A un arbre binaire complet, nous avons vu que :
\(\tau = 2^{h + 1} - 1\)
On en déduit donc que :
\(h + 1 \leq \tau \leq 2^{h + 1} - 1\)
Arbres binaires de recherche¶
La recherche d’un élément dans un arbre a une complexité de l’ordre du nombre d’éléments \(\tau\). Ce n’est pas mieux qu’une liste ! On cherche donc à optimiser la structure.
Définition
Un arbre binaire de recherche (ABR) est un arbre qui vérifie :
- Tous les éléments du sous-arbre gauche sont strictement inférieurs à la racine.
- Tous les éléments du sous-arbre droite sont strictement supérieurs à la racine.
- Les deux sous-arbres sont des arbres binaires de recherche.
Exercice
Parmi les arbres ci-dessous, détérminez ceux qui sont des arbres binaires de recherche :
a) 
b) 
Un arbre binaire est équilibré si tous les chemins de la racine aux feuilles ont pour longueur \(h\) ou \(h-1\) .
Arbre équilibré
Parmi les arbres binaires de recherche ci-dessous, déterminez ceux qui sont équilibrés :
a) 
b) 
Algorithmie¶
Savoir utiliser la récursivité pour résoudre des problèmes algorithmiques sur les arbres binaires est fondamental dans ce cours.
Calcul de la hauteur et de la taille et de la hauteur (vu en TD et TP)¶
La taille \(\tau\) d'un arbre \(A\) se calcule récursivement :
A chaque appel, on renvoie 1 + taille(gauche(A)) + taille(droite(A)).
Dans le cas de base, en cas d’absence de noeud, on renvoie 0.
La hauteur \(h\) d'un arbre \(A\) se calcule récursivement :
- un arbre vide a une hauteur de -1 (ou 0 en fonction de la convention choisie)
- un arbre non vide a pour hauteur 1 + la hauteur maximale de ses deux sous'arbres
Pseudo-code :
hauteur(Arbre A) :
Si A vide
retourner - 1
retourner 1 + max(hauteur(gauche(A)), hauteur(droite(A)))
Parcours de l'arbre¶
Parcours en profondeur (vu en TD et TP)¶
On cherche à parcourir les nœuds d’un arbre. Le parcours en profondeur traite les enfants en priorité.
Principe de l’algorithme :
- Si l’arbre est vide, on s’interrompt
- Sinon, selon l’ordre de priorité choisi : ➢ On traite la racine ➢ On parcourt récursivement le sous-arbre gauche ➢ On parcourt récursivement le sous-arbre droit
Suivant l’ordre de traitement des deux sous-arbres par rapport à la racine, nous avons en réalité trois parcours en profondeur différent :
- le parcours préfixe traite la racine avant les deux sous-arbres
- le parcours infixe traite la racine entre les deux sous-arbres
- le parcours postfixe traite la racine après les deux sous-arbres
Parcours en largeur (vu en TD)¶
Le parcours en largeur (BFS pour Breadth First Search) consiste à parcourir l'arbre niveau par niveau.
Algorithmie sur les arbres binaires de recherche¶
Recherche d'une clé¶
Les arbres binaires de recherche sont très utilisés car ils permettent de retrouver et d'insérer des données rapidement. On les retrouve par exemple logiquement dans les SGBD (Système de Gestion de Bases de Données).
Nous allons rappeler le principe de la recherche dichotomique qui est censé avoir été vu en première.
Lorsque l'on est en présence d'un tableau qui contient des données triées :
Et que l'on souhaite chercher une valeur dans ce tableau, alors on pourra utiliser ce qu'on appelle une recherche dichotomique.
Définition du dictionnaire "Larousse"
Dichotomique : qui se divise et se subdivise de deux en deux, qui repose sur une division binaire : Classification dichotomique.
Cela consiste à diviser à chaque fois le tableau en deux et à vérifier si l'élément au milieu du tableau est inférieur ou supérieur à la valeur que l'on recherche.
Etant donné que l'on divise l'espace de recherche par deux à chaque itération la complexité algorithmique de cet algorithmique est de \(O(log_2(n))\), contre \(O(n)\) si on parcours chacun des éléments du tableau un à un.
Dans le cas d'un arbre binaire de recherche pour que la recherche se fasse en \(O(log_2(n))\) l'arbre doit être équilibré. Dans le pire des cas cette complexité sera de \(O(n)\), pensez par exemple au cas d'un arbre binaire de recherche qui serait filiforme.
On peut alors éliminer la moitié de l’arbre à chaque itération. Contrairement à un tableau (une liste Python) l'insertion peut également se faire en \(O(log_2(n))\).
recherche_cle : Recherche d'une clé
_________________________
entrée : A, un arbre binaire de recherche
entrée : clé, la clé (valeur) recherchée
sortie : Vrai si la clé (valeur) recherchée est dans l'arbre, Faux sinon.
_________________________
Si A est vide
Sortir : Faux
Si A.racine = clé
Sortir : Vrai
Si A.racine < clé
Sortir : recherche_cle(A.gauche, clé)
Si A.racine > clé
Sortir : recherche_cle(A.droite, clé)
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.
inserer_cle : Insérer une clé
_________________________
entrée : A, un arbre binaire de recherche
entrée : clé, la clé (valeur) à insérer
_________________________
Si A est vide
A.racine = clé
Si clé < A.racine.valeur
inserer_cle(A.sous_arbre_gauche, clé)
Si clé > A.racine.valeur
inserer_cle(A.sous_arbre_droit, clé)