32. Binary Search Trees (BSTs - Arbres Binaires de Recherche) : Insertion et Recherche

Un Binary Search Tree (BST) est un type spécial d'arbre binaire qui organise les données pour une recherche, une insertion et une suppression efficaces.

La Propriété du BST

Pour chaque nœud X dans l'arbre :

1. La valeur de tous les nœuds dans son sous-arbre gauche doit être inférieure à la valeur de X.
2. La valeur de tous les nœuds dans son sous-arbre droit doit être supérieure à la valeur de X.

Opération de Recherche

1. Commencer à la racine.
2. Si la cible est égale au nœud actuel, retourner vrai.
3. Si la cible est plus petite, se déplacer vers l'enfant gauche.
4. Si la cible est plus grande, se déplacer vers l'enfant droit.

Efficacité

• Cas Moyen (Arbre Équilibré) : La recherche, l'insertion et la suppression sont O(log N). (Efficacité similaire à la Binary Search sur un tableau).
• Pire Cas (Arbre Asymétrique - Skewed Tree) : Si les données sont insérées dans un ordre trié, l'arbre devient une linked list et la complexité se dégrade à O(N).