🌳 Introduction aux Arbres Binaires (Binary Tree - BT)

Les arbres binaires sont des structures de données hiérarchiques où chaque nœud a au maximum deux enfants. Ils sont fondamentaux en informatique pour organiser et manipuler des données de manière efficace.

📚 Qu'est-ce qu'un Arbre Binaire ?

Un arbre binaire est une structure de données arborescente où chaque nœud peut avoir jusqu'à deux enfants :

Enfant gauche
Enfant droit

Les arbres binaires peuvent être de différents types :

Arbre binaire complet : Tous les niveaux sont complètement remplis, sauf peut-être le dernier, qui est rempli de gauche à droite.
Arbre binaire parfait : Tous les niveaux sont complètement remplis.
Arbre binaire dégénéré : Chaque nœud a exactement un enfant, ressemblant à une liste chaînée.

🔍 Qu'est-ce qu'un Arbre Binaire de Recherche (BST) ?

Un arbre binaire de recherche (BST) est un type particulier d'arbre binaire qui suit une propriété spécifique :

Le sous-arbre gauche d'un nœud contient uniquement des nœuds avec des valeurs inférieures à celle du nœud.
Le sous-arbre droit d'un nœud contient uniquement des nœuds avec des valeurs supérieures à celle du nœud.

🛠️ Où Utiliser les Arbres Binaires et les BST ?

Les arbres binaires et les BST sont utilisés dans de nombreux domaines :

📚 Structures de données et algorithmes de tri : Tables de symboles, dictionnaires, etc.
🔍 Applications de recherche : Bases de données, systèmes de fichiers.
🧮 Expressions arithmétiques : Représentation des expressions mathématiques.
🌐 Parcours de graphes : Algorithmes DFS et BFS.

📊 Analyse de Complexité

Pour un BST équilibré :

Opération	Complexité (Cas Équilibré)	Complexité (Cas Dégradé)
Recherche	O(log n)	O(n)
Insertion	O(log n)	O(n)
Suppression	O(log n)	O(n)

💻 Implémentation en Python

Voici une implémentation d'un Binary Search Tree (BST) :

class Node:
    def __init__(self, valeur):
        self.valeur = valeur
        self.gauche = None
        self.droit = None

class BST:
    def __init__(self):
        self.racine = None

    # Insertion d'une valeur dans le BST
    def inserer(self, valeur):
        if self.racine is None:
            self.racine = Node(valeur)
        else:
            self._inserer_recursif(self.racine, valeur)

    def _inserer_recursif(self, noeud, valeur):
        if valeur < noeud.valeur:
            if noeud.gauche is None:
                noeud.gauche = Node(valeur)
            else:
                self._inserer_recursif(noeud.gauche, valeur)
        else:
            if noeud.droit is None:
                noeud.droit = Node(valeur)
            else:
                self._inserer_recursif(noeud.droit, valeur)

    # Recherche d'une valeur dans le BST
    def rechercher(self, valeur):
        return self._rechercher_recursif(self.racine, valeur)

    def _rechercher_recursif(self, noeud, valeur):
        if noeud is None or noeud.valeur == valeur:
            return noeud is not None
        if valeur < noeud.valeur:
            return self._rechercher_recursif(noeud.gauche, valeur)
        else:
            return self._rechercher_recursif(noeud.droit, valeur)

    # Affichage en ordre croissant (parcours en ordre)
    def parcours_en_ordre(self):
        self._parcours_en_ordre_recursif(self.racine)

    def _parcours_en_ordre_recursif(self, noeud):
        if noeud is not None:
            self._parcours_en_ordre_recursif(noeud.gauche)
            print(noeud.valeur, end=" ")
            self._parcours_en_ordre_recursif(noeud.droit)

# Utilisation du BST
bst = BST()
bst.inserer(10)
bst.inserer(5)
bst.inserer(15)
bst.inserer(7)

print("Recherche 7 dans le BST :", bst.rechercher(7))  # Sortie : True
print("Recherche 3 dans le BST :", bst.rechercher(3))  # Sortie : False

print("Parcours en ordre croissant : ", end="")
bst.parcours_en_ordre()  # Sortie : 5 7 10 15

Explication du Code :

inserer : Insère une valeur en maintenant la propriété du BST.
rechercher : Recherche une valeur dans le BST.
parcours_en_ordre : Affiche les valeurs en ordre croissant.

💪 Exercices

Testez vos connaissances avec ces exercices :

# Exercices :

# 1. Implémentez des fonctions pour les parcours en pré-ordre, en post-ordre et en largeur d'un arbre binaire.

# 2. Écrivez une fonction pour supprimer un nœud dans un BST tout en maintenant la propriété de recherche.

# 3. Créez une fonction pour vérifier si un arbre binaire est un arbre binaire de recherche valide.

# 4. Implémentez un algorithme pour équilibrer un arbre binaire de recherche.

# 5. Écrivez un programme pour trouver le chemin le plus court entre deux nœuds dans un arbre binaire.

🎉 Conclusion

Les arbres binaires et les arbres binaires de recherche sont des structures de données essentielles pour organiser et manipuler des données de manière efficace. Comprendre leur fonctionnement est crucial pour tout programmeur souhaitant maîtriser les algorithmes et les structures de données avancées.

Leçons