Qu'est-ce qu'un arbre binaire de recherche (BST) et quelles sont les complexités de ses opérations ?

Question

Accepted Answer

Un **arbre binaire de recherche** est un arbre binaire avec un invariant d'ordre : pour chaque nœud, **toutes les clés du sous-arbre gauche sont plus petites**, et **toutes les clés du sous-arbre droit sont plus grandes**. Cela vous permet de chercher en divisant le problème par deux à chaque étape.

## L'invariant

```text
        8
       / \
      3    10
     / \     \
    1   6     14     left < node < right at every node
```

## Recherche et insertion

```python
def search(node, key):
    while node:
        if key == node.val: return node
        node = node.left if key < node.val else node.right  # go one way
    return None

def insert(node, key):
    if node is None: return Node(key)
    if key < node.val: node.left  = insert(node.left, key)
    else:              node.right = insert(node.right, key)
    return node
```

## Complexité

| Opération | Équilibré | Pire (dégénéré) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |

Le **pire cas** se produit quand les clés sont insérées dans l'ordre trié — l'arbre dégénère en une liste chaînée de hauteur `n`.

## Compromis

- **Avantages :** parcours ordonné en O(n) ; supporte les requêtes de plage et successeur/prédécesseur.
- **Inconvénients :** aucune garantie d'équilibre en soi — nécessite une variante AVL ou red-black pour rester O(log n).

## Pourquoi c'est important

Les BST vous donnent des données triées et dynamiques avec des opérations logarithmiques — l'ancêtre conceptuel des index de base de données et des maps ordonnées.

Le problème de dégénérescence motive les **arbres auto-équilibrés**, un sujet de suivi clé dans les entretiens.