Arbres binaires: Définition et parcours

• Un arbre binaire est une structure de données hiérarchique où chaque nœud a au plus deux enfants, appelés enfant gauche et enfant droit.

Définition des arbres binaires

• Un arbre binaire est composé d'un nœud racine.
• Chaque nœud peut avoir zéro, un ou deux enfants.
• Les enfants sont désignés comme enfant gauche et enfant droit.
• Si un nœud n'a pas d'enfants, il est appelé une feuille.
• Un arbre vide est aussi un arbre binaire.
• La profondeur d'un nœud est la longueur du chemin de la racine à ce nœud.
• La hauteur d'un arbre est la profondeur maximale de ses feuilles.

Parcours des arbres binaires

• Le parcours d'arbre est le processus de visiter chaque nœud de l'arbre exactement une fois.
• Il existe deux principaux types de parcours : en profondeur (DFS) et en largeur (BFS).

Parcours en profondeur (DFS)

• Explore autant que possible chaque branche avant de revenir en arrière.
• Trois types principaux : préfixe (pré-ordre), infixe (en-ordre), et suffixe (post-ordre).
  • Préfixe : visiter le nœud, puis parcourir le sous-arbre gauche, puis le sous-arbre droit.
  • Infixe : parcourir le sous-arbre gauche, visiter le nœud, puis parcourir le sous-arbre droit. Utilisé fréquemment dans les arbres binaires de recherche pour obtenir les nœuds dans l'ordre trié.
  • Suffixe : parcourir le sous-arbre gauche, puis le sous-arbre droit, puis visiter le nœud.

Parcours en largeur (BFS)

• Explore tous les nœuds à la profondeur actuelle avant de passer à la profondeur suivante.
• Utilise une file d'attente pour suivre les nœuds à visiter.

Applications des arbres binaires

• Les arbres binaires sont utilisés dans divers domaines de l'informatique.
• Arbres binaires de recherche (BST) : stockage et recherche efficaces de données triées.
  • Permettent des opérations de recherche, d'insertion et de suppression en temps logarithmique moyen.
• Arbres de Huffman : compression de données.
  • Utilisés pour créer des codes de longueur variable pour représenter des caractères, les caractères les plus fréquents ayant des codes plus courts.
• Arbres d'expression : représentation d'expressions arithmétiques.
  • Les nœuds internes sont des opérateurs et les feuilles sont des opérandes.
• Arbres de décision : algorithmes d'apprentissage automatique.
  • Utilisés pour la classification et la régression en divisant l'ensemble de données en sous-ensembles plus petits basés sur des caractéristiques spécifiques.

Équilibre des arbres binaires

• Un arbre binaire est équilibré si la différence de hauteur entre ses sous-arbres gauche et droit est d'au plus 1 pour chaque nœud.
• Les arbres équilibrés garantissent des performances optimales pour les opérations de recherche, d'insertion et de suppression.
• Exemples d'arbres équilibrés :
  • Arbres AVL : arbres auto-équilibrés où la différence de hauteur entre les sous-arbres gauche et droit est d'au plus 1.
  • Arbres rouge-noir : arbres auto-équilibrés utilisant des bits de couleur pour maintenir l'équilibre.

Annexes des arbres binaires

• Implémentation en Python(exemple)

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def insert(root, data):
    if root is None:
        return Node(data)
    else:
        if data < root.data:
            root.left = insert(root.left, data)
        else:
            root.right = insert(root.right, data)
        return root

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.data, end=" ")
        inorder_traversal(root.right)

## Exemple d'utilisation
root = None
root = insert(root, 50)
insert(root, 30)
insert(root, 20)
insert(root, 40)
insert(root, 70)
insert(root, 60)
insert(root, 80)

print("Parcours infixe de l'arbre :")
inorder_traversal(root)

• Complexité temporelle des opérations :
  • Recherche dans un arbre binaire de recherche équilibré : O(log n) en moyenne, O(n) dans le pire des cas (arbre dégénéré).
  • Insertion dans un arbre binaire de recherche équilibré : O(log n) en moyenne, O(n) dans le pire des cas.
  • Suppression dans un arbre binaire de recherche équilibré : O(log n) en moyenne, O(n) dans le pire des cas.
• Les arbres binaires peuvent être étendus pour inclure des informations supplémentaires dans chaque nœud, telles que des pointeurs vers le nœud parent ou des informations de couleur pour les arbres auto-équilibrés.