Les arbres binaires

Pr. EL HADIQ Zouhair

Terminologie · implémentation · parcours · ABR · tas

1 / 12

Pourquoi les arbres ?INTRO

Une structure de données hiérarchique : un parent, des enfants.

Systèmes de fichiers, arbres généalogiques, taxonomies.
Arbres syntaxiques, arbres de décision, indexation de bases de données.

Arbre binaire. Chaque nœud a au plus deux fils : gauche et droit.

2 / 12

VocabulaireDÉFINITIONS

Terme	Sens
Racine	nœud sans parent
Feuille	nœud sans fils (degré 0)
Nœud interne	au moins un fils
Degré	nb de fils (0, 1 ou 2)
Profondeur	distance à la racine
Hauteur	profondeur max

3 / 12

Hauteur et profondeurMESURES

Profondeur d'un nœud : nb d'arêtes jusqu'à la racine (racine à 0).
Hauteur de l'arbre : profondeur maximale. Arbre vide $h=-1$.

Pour $n$ nœuds et hauteur $h$ : $\quad h+1 \le n \le 2^{h+1}-1$

Arbre filiforme : $h = n-1$. Arbre parfait/équilibré : $h \approx \log_2 n$.

def hauteur(a): if a is None: return -1 return 1 + max(hauteur(a[1]), hauteur(a[2]))

4 / 12

Implémentation en PythonLISTES

Un arbre $=$ None (vide) ou [valeur, gauche, droite].

# Exemple : 4 # / \ # 2 6 arbre = [4, [2, None, None], [6, None, None]] def nb_noeuds(a): if a is None: return 0 return 1 + nb_noeuds(a[1]) + nb_noeuds(a[2])

a[0] valeur · a[1] sous-arbre gauche · a[2] sous-arbre droit.

5 / 12

Parcours en profondeurDFS

Trois ordres selon le moment où l'on traite la racine :

Parcours	Ordre	Sur l'exemple
Préfixe	R → G → D	4 2 1 3 6 5 7
Infixe	G → R → D	1 2 3 4 5 6 7
Postfixe	G → D → R	1 3 2 5 7 6 4

def infixe(a): if a is None: return [] return infixe(a[1]) + [a[0]] + infixe(a[2])

6 / 12

Parcours en largeurBFS

Niveau par niveau, de gauche à droite, à l'aide d'une file (FIFO).

from collections import deque def largeur(a): if a is None: return [] file, ordre = deque([a]), [] while file: n = file.popleft() ordre.append(n[0]) if n[1]: file.append(n[1]) if n[2]: file.append(n[2]) return ordre

Profondeur → pile (récursion) | largeur → file.

7 / 12

Arbre binaire de rechercheABR

En tout nœud : gauche < nœud < droite.

L'invariant d'ordre permet une recherche dichotomique en $O(h)$.

def recherche(a, x): if a is None: return False if x == a[0]: return True if x < a[0]: return recherche(a[1], x) return recherche(a[2], x)

8 / 12

Insertion dans un ABRABR

def inserer(a, x): if a is None: return [x, None, None] if x < a[0]: a[1] = inserer(a[1], x) elif x > a[0]: a[2] = inserer(a[2], x) return a

Insérer puis parcourir en infixe $\Rightarrow$ liste triée (tri par arbre).

Pire cas (valeurs déjà triées) : arbre filiforme, $h = n-1$, recherche en $O(n)$.

9 / 12

Le tas (heap)VARIANTE

Arbre binaire complet + propriété de tas. Tas-max : parent $\ge$ fils.

Rangé dans une liste : fils de $i$ en $2i{+}1$ et $2i{+}2$, père en $\lfloor (i-1)/2 \rfloor$.

def inserer_tas(t, x): t.append(x); i = len(t) - 1 while i > 0 and t[(i-1)//2] < t[i]: p = (i-1)//2 t[i], t[p] = t[p], t[i]; i = p return t

Support des files de priorité : insertion/extraction du max en $O(\log n)$.

10 / 12

Complexités à retenirBILAN

Opération	Coût
Parcours (DFS / BFS)	$O(n)$
Hauteur, nb de nœuds	$O(n)$
Recherche / insertion ABR (équilibré)	$O(\log n)$
Recherche / insertion ABR (pire cas)	$O(n)$
Insertion / extraction-max tas	$O(\log n)$

11 / 12

À retenirSYNTHÈSE

Définition récursive : vide ou racine + 2 sous-arbres.
Parcours profondeur (préfixe/infixe/postfixe) et largeur.
ABR : gauche < nœud < droite ; infixe trié ; $O(h)$.
Tas : arbre complet en tableau ; file de priorité.

Idée centrale. La récursivité de la structure se traduit directement en récursivité des algorithmes.

12 / 12