Un Arbre Binaire de Recherche (ABR), ou Binary Search Tree (BST), est un Arbre Binaire tel que :
les clés du sous-arbre gauche sont inférieures ou égales à celle de la racine
les clés du sous-arbre droit sont supérieures ou égales à celle de la racine
les deux sous-arbres sont eux-mêmes des Arbres Binaires de Recherche
Les Clés d'un Arbre Binaire de Recherche sont ses étiquettes
Remarque : L'égalité est ici possible pour le sous-arbre gauche (le sous-arbre droit a des clés strictement supérieures), mais on pourrait tout aussi bien faire le contraire.
de la Recherche d'une Clé Cible dans un ABR quelconque
Dans un Arbre Binaire de Recherche (ABR) quelconque, l'unique chemin menant vers la Clé Cible (à partir de la racine) est obligatoirement calculable/parcourable de la manière suivante:
Pour chaque noeud courant de chaque niveau parcouru :
Si la Clé Cible = clé du noeud courant du niveau, Alors on a bien trouvé la Clé Cible sur le niveau courant
Si la Clé Cible \(<\) clé du noeud courant du niveau, Alors la Recherche se poursuit dans le sous-arbre gauche du noeud
Si la Clé Cible \(>\) clé du noeud courant du niveau, Alors la Recherche se poursuit dans le sous-arbre droit du noeud
Lorsqu'on arrive au dernier niveau de cet unique chemin parcouru (le noeud est une feuille) mais sans avoir trouvé le nombre Cible, cela prouve que la Clé Cible n'existe nulle part dans l'ABR (inutile de vérifier les autres chemins à partir de la racine)
Concernant la Complexité :
Complexité de Recherche d'un nombre dans un ABR quelconque
Dans un ABR quelconque, dans le pire des cas, la complexité en temps de la Recherche d'une Clé Cible est en \(O(h)\), càd proportionnelle à sa hauteur \(h\)
Limitation des ABR quelconques
Malheureusement, l'algorithme de Recherche d'une clé dans un ABR n'est pas efficace lorsque l'ABR est quelconque, en effet il existe :
des ABR non équilibrés,
voire pire (cas extrême) : des ABR dégénérés (arbres peignes),
Dans chacun de ces deux cas, la hauteur \(h\) est égale à la taille \(n\) de l'arbre.
Donc dans le pire des cas (où \(h=n\)), la complexité de la recherche d'une clé cible dans un ABR est linéaire en \(n\), càd est en \(O(n)\), donc aussi mauvais que pour les Listes et/ou les Files.
D'ailleurs un ABR Peigne peut être considéré comme une Liste, ou une File.
Pour éviter cela, il suffit d'empêcher les ABR d'être des Peignes, et plus généralement empêcher les ABR d'être non équilibrés.
C'est pourquoi dans la suite, on s'intéressera à des Arbres Binaires de Recherche Équilibrés, que nous appelerons des Arbres AVL.
L'Insertion d'un noeud (avec sa clé) se déroule en deux étapes : la Recherche de la position où insérer le noeud dans l'ABR : Dans le pire des cas, en \(O(h)\) l'Insertion : Dans le pire des cas, en \(O(1)\)
Durant la Recherche de la position où l'insérer :
Soit on trouve que cette clé existe déjà dans l'arbre, auquel cas :
On insère la nouvelle clé (doublon) comme fils gauche du noeud contenant la clé (par convention, et en général),
le SAG de la clé doublon devient le SAG de la nouvelle clé après son insertion
Soit on arrive à une feuille : on ajoute alors le nouveau noeud comme fils de la feuille en comparant sa clé à celle de la feuille :
Si clé nouveau noeud \(\le\) clé feuille, Alors le nouveau noeud sera à gauche de la feuille
Si clé nouveau noeud \(>\) noeud feuille, Alors le nouveau noeud sera à droite de la feuille
donc :
Complexité Insertion dans un ABR quelconque
Dans un ABR quelconque, dans le pire des cas, La complexité de l'Insertion est en \(O(h)\)
AVANT insertion de 2 : ABR équilibré
$$\Rightarrow$$
APRÈS insertion de 2 : ABR déséquilibré
Remarque
L'Insertion d'une clé dans un ABR est compatible avec la structure d'ABR, autrement dit : Après insertion d'une clé, un arbre ABR reste un arbre ABR.
ATTENTION Par contre, L'insertion d'une clé peut casser l'équilibre dans un ABR
Suppression d'une Feuille (Exemple : Suppression de la Feuille \(67\) )
ABR quelconque BUT : Supprimer 67
1. Recherche de 67
2. On supprime la Feuille
ABR quelconque APRÈS Suppression de 67 La suppression d'une Feuille ne déséquillibre pas l'ABR (plus qu'il ne l'était déjà)
Suppression d'un noeud à \(1\) seul enfant (Exemple: Suppression de \(70\) )
ABR quelconque BUT : Supprimer 70
:one: Recherche de 70 :two: Déterminer 68 = son unique enfant :three: On supprime le noeud
ABR quelconque APRÈS Suppression de 70 La suppression d'un noeud à 1 seul enfant peut déséquillibrer l'ABR (plus qu'il ne l'était déjà)
Suppression d'un noeud à \(2\) enfants
Suppression, puis Remplacement par le max des min
ABR quelconque BUT : Supprimer 50
:one: Recherche de 50 :two: Déterminer 44 = le max des min
ABR quelconque APRÈS Suppression de 50 + Remplacement par 44 = le max des min La suppression d'un noeud à 2 enfants peut déséquillibrer l'ABR (plus qu'il ne l'était déjà)
Suppression, puis Remplacement par le min des max
ABR quelconque BUT : Supprimer 50
:one: Recherche de 50 :two: Déterminer 51 = le min des max
ABR quelconque APRÈS Suppression de 50 + Remplacement par 51 = le min des max La suppression d'un noeud à 2 enfants peut déséquillibrer l'ABR (plus qu'il ne l'était déjà)
Suppression d'un noeud dans un ABR quelconque
La Suppression d'un noeud d'un ABR quelconque se fait en deux étapes: On Recherche la clé dans l'ABR : Dans le pire des cas, en \(O(h)\) On le Supprime : Dans le pire des cas, en \(O(1)\). Trois situations sont possibles:
Suppression d'une feuille : Il suffit de l'enlever de l'arbre puisqu'elle n'a pas de fils.
Suppression d'un noeud avec un enfant : Il faut l'enlever de l'arbre en le remplaçant par son unique fils (gauche ou droit).
Suppression d'un noeud \(N\) avec deux enfants : Dans ce cas, pour préserver la structure d'arbre ABR après la suppression du noeud \(N\), on peut :
Remplacer \(N\) par le plus grand des nombres plus petits que lui (le max des min): càd par le noeud le plus à droite du sous-arbre gauche de \(N\). Ou bien :
Remplacer \(N\) par le plus petit des nombres plus grands que lui (le min des max): càd par le noeud le plus à gauche du sous-arbre droit de \(N\).
Complexité de la Suppression dans un ABR quelconque
Dans un ABR quelconque, dans le pire des cas, La complexité de la Suppression est en \(O(h)\)
Remarque
AVANT suppression de 12 : ABR équilibré
APRÈS suppression de 12 : ABR déséquilibré
En choisissant correctement le remplaçant du noeud supprimé (par le max des min, ou par le min des max), la Suppression d'une clé dans un ABR est compatible avec la structure d'ABR, autrement dit : Après Suppression d'une clé, un arbre ABR reste un arbre ABR.
ATTENTION Par contre, La Suppression d'une clé peut casser l'équilibre dans un ABR
, ou 
, est un Arbre Binaire tel que :
la Recherche de la position où insérer le noeud dans l'ABR : Dans le pire des cas, en \(O(h)\)
l'Insertion : Dans le pire des cas, en \(O(1)\)
ATTENTION