Structure d'arbre
Un arbre est une structure de donnéesnon linéairequi simule la hiérarchie ramifiée des arbres dans la nature. Contrairement aux structures linéaires telles que les tableaux et les listes chaînées, où les éléments sont disposés les uns après les autres, les éléments de données dans un arbre (appelésnœud) il existe une relation hiérarchique claire de type un-à-plusieurs entre eux.
Structure d'arbreTout comme un vrai arbre :
- nœud racine: la partie racine de l'arbre, le seul nœud sans nœud parent
- nœud enfant: nœuds qui se ramifient à partir d'un nœud
- nœud feuille: un nœud sans enfants, comme une feuille
- chemin: le trajet d'un nœud à un autre nœud
- profondeur: la longueur du chemin depuis le nœud racine jusqu'à ce nœud
- hauteur: la longueur du chemin depuis ce nœud jusqu'au nœud feuille le plus éloigné
Analogie avec la vie :
- arbre généalogique: grands-parents → parents → enfants → petits-enfants
- structure organisationnelle: PDG → directeur → manager → employé
- système de fichiers: répertoire racine → sous-répertoire → fichier
- classification des livres: catégorie générale → sous-catégorie → livre spécifique
| type de structure | efficacité de recherche | efficacité d'insertion | efficacité de suppression | ordre |
|---|---|---|---|---|
| array | O(n) | O(n) | O(n) | Aucune |
| Liste chaînée | O(n) | O(1) | O(1) | Aucune |
| Table de hachage | O(1) | O(1) | O(1) | Aucune |
| arbre binaire de recherche | O(log n) | O(log n) | O(log n) | Oui |
Termes de base
Avant d'aller plus loin, familiarisons-nous d'abord avec la terminologie de base des arbres :

- Nœud: chaque élément d'un arbre. Il contient les données stockées et des liens vers ses nœuds enfants.
- Nœud racine: le nœud au sommet de l'arbre, le point de départ de tout l'arbre. Un arbre a exactement un nœud racine.
- Nœud parent et nœud enfant (Parent & Enfant): Si un nœud A est connecté à un nœud B situé en dessous, alors A est lenœud parentde B, B est lenœud enfantde A. Un nœud parent peut avoir plusieurs nœuds enfants.
- Nœuds frères (Frères et sœurs): les nœuds qui partagent le même nœud parent sont frères et sœurs.
- Nœud feuille (Feuille): un nœud sans nœuds enfants, aussi appelé nœud terminal.
- Arête: la ligne reliant deux nœuds, représentant la relation entre eux.
- Chemin: la séquence de nœuds traversés depuis le nœud racine jusqu'à un nœud spécifique.
- Hauteur: sur le plus long chemin d’un nœud à son nœud feuille le plus éloignénombre d’arêtes. La hauteur de l’arbre est la hauteur du nœud racine.
- Profondeur: sur le chemin du nœud racine à un nœud spécifiquenombre d’arêtes. La profondeur du nœud racine est 0.
- Niveau: tous les nœuds ayant la même profondeur appartiennent au même niveau. Le nœud racine est au niveau 0.
Propriétés de base des arbres
- chemin unique: il existe exactement un chemin entre deux nœuds quelconques d’un arbre.
- N nœuds, N-1 arêtes: un arbre avec N nœuds possède au total N-1 arêtes.
- acyclique: il n’y a pas de cycle dans un arbre (c’est-à-dire qu’en partant d’un nœud et en suivant les arêtes, on ne peut pas revenir à ce nœud).
Pourquoi avons-nous besoin des arbres ? — Avantages et applications des arbres
Vous pouvez vous demander : avec les tableaux et les listes chaînées, pourquoi avons-nous encore besoin des arbres ? La réponse réside dans l’efficacité.
- tableau: recherche rapide (via l’indice), mais insertion et suppression lentes (nécessite de déplacer de nombreux éléments).
- Liste chaînée: insertion et suppression rapides, mais recherche lente (nécessite un parcours depuis le début).
- Arbres (en particulier les arbres binaires de recherche): tout en maintenant les données ordonnées, ils peuvent offrir une vitesse de recherche bien plus rapide que les listes chaînées, et des opérations d’insertion/suppression plus efficaces que les tableaux.
Scénarios d'application pratiques:
- système de fichiers: les dossiers et les fichiers dans les ordinateurs sont organisés sous la forme d'un arbre.
- index de base de données: B-tree et B+ tree sont des structures de données essentielles pour des requêtes efficaces dans les bases de données.
- organigramme: la gestion hiérarchique d'une entreprise ou d'un département.
- arbre de décision: modèles de classification en intelligence artificielle et en apprentissage automatique.
- DOM HTML: le modèle d'objet du document d'une page web est un arbre.
Arbre binaire : le membre le plus important de la famille des arbres
Un arbre binaire est un arbre dans lequel chaque nœud a au plus deux nœuds enfants. Ces deux nœuds enfants sont généralement appelésnœud enfant gaucheetnœud enfant droit, il est à la base de nombreuses structures d'arbres puissantes (telles que les arbres de recherche binaires, les tas et les arbres AVL).
La structure de base est la suivante :

Termes de base des arbres binaires
| Terme | définition | Analogie avec la vie |
|---|---|---|
| nœud | l'unité de base contenant des données et des pointeurs | Une personne dans la famille |
| nœud racine | Le nœud supérieur d'un arbre | Ancêtre dans la famille |
| nœud parent | Un nœud avec des nœuds enfants | parents |
| nœud enfant | le nœud pointé par son nœud parent | children |
| nœud frère | nœuds enfants du même parent | frères |
| nœud feuille | un nœud sans enfants | une personne de la famille sans enfants |
| depth | le nombre d'arêtes de la racine à ce nœud | nombre de générations |
| height | le nombre d'arêtes de ce nœud au nœud feuille le plus éloigné | le nombre de générations pendant lesquelles la famille se poursuit |
type d'arbre binaire
| Type | Fonctionnalités | Complexité temporelle | scénarios d'application |
|---|---|---|---|
| arbre binaire ordinaire | chaque nœud a au plus 2 nœuds enfants | O(n) | arbre d'expression |
| arbre binaire strict | chaque nœud a soit 0 soit 2 nœuds enfants | O(n) | Codage de Huffman |
| arbre binaire complet | tous les niveaux sauf le dernier sont remplis | O(n) | implémentation d'un tas |
| arbre binaire de recherche | gauche < racine < droite | En moyenne O(log n) | Recherche, tri |
| arbre binaire équilibré | la différence de hauteur entre les sous-arbres gauche et droit est ≤ 1 | O(log n) | index de base de données |
| arbre rouge-noir | arbre équilibré coloré | O(log n) | noyau Linux |
Opérations sur les arbres binaires de recherche
| Opération | Description | Complexité temporelle |
|---|---|---|
| Rechercher | Rechercher un nœud par valeur | en moyenne O(log n), dans le pire O(n) |
| Insérer | insérer un nouveau nœud | en moyenne O(log n), dans le pire O(n) |
| Delete | Supprimer le nœud spécifié | en moyenne O(log n), dans le pire O(n) |
| parcours | Visiter tous les nœuds | O(n) |
Parcours d'arbre binaire
Le parcours consiste à visiter chaque nœud de l'arbre selon une certaine règle, et chaque nœud n'est visité qu'une seule fois. C'est la base des algorithmes liés aux arbres. Il existe principalement quatre façons :
Parcours pré-ordre:Racine -> Gauche -> Droite
- Visiter d'abord le nœud racine, puis parcourir récursivement en pré-ordre le sous-arbre gauche, et enfin parcourir récursivement en pré-ordre le sous-arbre droit.
- Application: Copier un arbre, obtenir une expression préfixe.
Parcours en ordre:Gauche -> Racine -> Droite
- D'abord parcourir récursivement en ordre le sous-arbre gauche, puis visiter le nœud racine, et enfin parcourir récursivement en ordre le sous-arbre droit.
- Application: dansarbre binaire de rechercheParmi eux, le parcours en ordre vaordre croissantafficher toutes les valeurs.
Parcours post-ordre:Gauche -> Droite -> Racine
- D'abord parcourir récursivement en post-ordre le sous-arbre gauche, puis parcourir récursivement en post-ordre le sous-arbre droit, et enfin visiter le nœud racine.
- Application: supprimer un arbre, calculer la taille d'un répertoire.
Parcours par niveaux:Par niveau, de gauche à droite
- En partant du nœud racine, visiter les nœuds niveau par niveau.
- Application: traiter les données par niveaux (par exemple, imprimer un organigramme).Il est généralement implémenté à l'aide d'une file (Queue).。

Exemple: Pour l'arbre binaire ci-dessous, les résultats de parcours sont les suivants :
1
/ \
2 3
/ \ \
4 5 6
- préordre:1, 2, 4, 5, 3, 6
- en ordre:4, 2, 5, 1, 3, 6
- post-ordre:4, 5, 2, 6, 3, 1
- ordre par niveau:1, 2, 3, 4, 5, 6
Exercice : implémenter un arbre binaire en Python
Assez de théorie, écrivons du code ! Nous allons implémenter une classe simple de nœud d'arbre binaire et compléter les opérations d'insertion et de parcours.
Étape 1 : Définir la classe de nœud
Chaque nœud doit stocker des données et pointer vers ses nœuds enfants gauche et droit.
Exemple
"""Classe de nœud d'arbre binaire"""
def __init__(self, value):
self.value = value # Données stockées dans le nœud
self.left = None # Pointe vers le nœud enfant gauche
self.right = None # Pointe vers le nœud enfant droit
def __str__(self):
"""Pratique pour afficher les informations du nœud"""
return f"Node({self.value})"
Étape 2 : Construire un arbre d'exemple
Construisons manuellement l'arbre à partir du diagramme d'exemple précédent.
Exemple
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
node6 = TreeNode(6)
# Établir les relations de connexion (Liens)
root.left = node2
root.right = node3
node2.left = node4
node2.right = node5
node3.right = node6
print(f"Nœud racine : {root}")
print(f"Enfant gauche du nœud racine : {root.left}")
print(f"Enfant droit du nœud racine : {root.right}")
Étape 3 : Implémenter les algorithmes de parcours (version récursive)
La récursivité est la façon la plus intuitive d'implémenter le parcours d'arbre.
Exemple
"""Parcours préfixe : racine -> gauche -> droite"""
if node is None:
return
print(node.value, end=' ') # 1. Visiter le nœud racine
preorder_traversal(node.left) # 2. Parcourir le sous-arbre gauche
preorder_traversal(node.right) # 3. Parcourir le sous-arbre droit
def inorder_traversal(node):
"""Parcours infixe : gauche -> racine -> droite"""
if node is None:
return
inorder_traversal(node.left) # 1. Parcourir le sous-arbre gauche
print(node.value, end=' ') # 2. Visiter le nœud racine
inorder_traversal(node.right) # 3. Parcourir le sous-arbre droit
def postorder_traversal(node):
"""Parcours suffixe : gauche -> droite -> racine"""
if node is None:
return
postorder_traversal(node.left) # 1. Parcourir le sous-arbre gauche
postorder_traversal(node.right) # 2. Parcourir le sous-arbre droit
print(node.value, end=' ') # 3. Visiter le nœud racine
print("\n--- Démo de parcours ---")
print("Résultat du parcours préfixé :", end=' ')
preorder_traversal(root) # Sortie : 1 2 4 5 3 6
print("\nRésultat du parcours infixé :", end=' ')
inorder_traversal(root) # Sortie : 4 2 5 1 3 6
print("\nRésultat du parcours suffixé :", end=' ')
postorder_traversal(root) # Sortie : 4 5 2 6 3 1
Étape 4 : implémenter le parcours en largeur (en utilisant une file)
Le parcours en largeur doit utiliser la propriété "premier entré, premier sorti" d'une file.
Exemple
def level_order_traversal(root):
"""Parcours en largeur : utilisation d'une file"""
if root is None:
return
queue = deque([root]) # Initialiser la file et enfiler le nœud racine
while queue:
current_node = queue.popleft() # 1. Retirer le nœud de la gauche de la file
print(current_node.value, end=' ') # 2. Visiter ce nœud
# 3. Ajouter les nœuds enfants de ce nœud (s'il y en a) du côté droit de la file dans l'ordre
if current_node.left:
queue.append(current_node.left)
if current_node.right:
queue.append(current_node.right)
print("\nRésultat du parcours en largeur :", end=' ')
level_order_traversal(root) # Output: 1 2 3 4 5 6
Pratique et défi
Félicitations pour avoir terminé l'apprentissage de base ! Pour vraiment maîtriser les arbres, une pratique concrète est essentielle.
Exercice 1 : Calculer la hauteur de l'arbre
Écrire une fonctiontree_height(node), prend le nœud racine d'un arbre et renvoie la hauteur de l'arbre (la hauteur d'un arbre vide est -1 ou 0, par convention ; dans cet exemple, nous la définissons comme le nombre d'arêtes).
Indice: hauteur de l'arbre = 1 + max(hauteur du sous-arbre gauche, hauteur du sous-arbre droit). C'est un problème récursif classique.
Exercice 2 : Rechercher une valeur dans un arbre binaire
Écrire une fonctionsearch_in_tree(node, target_value), dans l'arbre binaire donné, recherchez s'il existe une valeur égale autarget_valuenœud. Si trouvé, renvoyerTrue, sinon renvoyerFalse。
Indice: on peut utiliser n'importe quelle méthode de parcours, et comparer la valeur de chaque nœud lorsqu'on le visite.
Défi : Arbre binaire de recherche (ABR)
Il s'agit d'une variante classique de l'arbre binaire. Dans un arbre binaire de recherche, pour tout nœud :
- sonsous-arbre gaucheles valeurs de tous les nœuds dans<La valeur de ce nœud.
- sonsous-arbre droitles valeurs de tous les nœuds dans>La valeur de ce nœud.
Votre défi est :
- Implémentation
insert_into_bst(root, value)fonction, insérez une valeur à la position correcte dans l'arbre binaire de recherche. - Implémentation
search_in_bst(root, value)fonction, qui utilise les propriétés de l'ABR pour une recherche efficace (complexité temporelle moyenne O(log N)).