Algorithmes Python

Arbre binaire de recherche en Python

Un arbre binaire de recherche range les valeurs plus petites dans le sous-arbre gauche et les plus grandes dans le sous-arbre droit, donc chaque comparaison élimine la moitié de l'arbre restant.

Qu’est-ce que Arbre binaire de recherche en Python ?

Un arbre binaire de recherche range les valeurs plus petites dans le sous-arbre gauche et les plus grandes dans le sous-arbre droit, donc chaque comparaison élimine la moitié de l'arbre restant.

Construisez un arbre binaire de recherche en Python : insérez des valeurs, recherchez-les et affichez-les dans l'ordre.

Quand l’utiliser ?

Comprendre les algorithmes et structures de données.
Observer chaque étape et traiter les cas limites.
Comparer temps d’exécution et mémoire.

Voir comment ça marche

Insérez des valeurs pour voir où elles se placent, cherchez une valeur pour suivre son chemin, et lancez un parcours pour voir l'ordre de visite.

Code d’exemple

Exécuter le code →

main.py

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None   # smaller values go left
        self.right = None  # larger values go right


def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node


def contains(node, value):
    # Each comparison discards one whole subtree.
    while node is not None:
        if value == node.value:
            return True
        node = node.left if value < node.value else node.right
    return False


def inorder(node):
    # Left subtree, node, right subtree: visits values in sorted order.
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)


def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)

print("inorder:", inorder(root))
print("contains 60:", contains(root, 60))
print("contains 65:", contains(root, 65))
print("height:", height(root))

Résultat attendu

inorder: [20, 30, 40, 50, 60, 70, 80]
contains 60: True
contains 65: False
height: 3

Fonctionnement

insert() descend depuis la racine et accroche la valeur à sa place. contains() suit un seul chemin, ce qui prend O(log n) étapes dans un arbre équilibré. Un parcours infixe (inorder) visite gauche, nœud, droite, donc les valeurs sortent triées.

Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.

Exercices pratiques

Modifiez les entrées et testez les cas limites avant d’utiliser des données plus volumineuses.

Testez une entrée vide, un élément et des doublons.
Affichez l’état après chaque étape.
Comparez les performances avec une autre solution.

Exécuter dans l’IDE Python →

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis