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

  1. chemin unique: il existe exactement un chemin entre deux nœuds quelconques d’un arbre.
  2. N nœuds, N-1 arêtes: un arbre avec N nœuds possède au total N-1 arêtes.
  3. 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 :

  1. 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.
  2. 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.
  3. 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.
  4. 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

class TreeNode:
    """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

# Créer un nœud
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

def preorder_traversal(node):
    """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

from collections import deque

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 :

  1. Implémentationinsert_into_bst(root, value)fonction, insérez une valeur à la position correcte dans l'arbre binaire de recherche.
  2. Implémentationsearch_in_bst(root, value)fonction, qui utilise les propriétés de l'ABR pour une recherche efficace (complexité temporelle moyenne O(log N)).
autres extensions