6.5 Arbres binaires de recherche randomisés
261
des performances acceptables, nous allons alors choisir d’insérer une nouvelle clé
soit dans une feuille de l’arbre complété (appelons-la f ) comme cela a été supposé
dans les sections 6.1 et 6.2, soit sur le chemin allant de la racine à f, en réorganisant
l’arbre en fonction de cette insertion. Le choix de la place où insérer sera aléatoire,
et nous verrons qu’il est possible de le faire sous une loi de probabilité choisie pour
que l’arbre binaire de recherche obtenu soit de loi Ord, i.e., que sa forme suive la
loi de l’arbre bourgeonnant.
Il nous faut d’abord indiquer comment insérer une clé à la racine d’un arbre
binaire de recherche ; il sera alors possible d’insérer une clé en tout nœud d’un
chemin de la racine vers une feuille, en l’insérant à la racine du sous-arbre enraciné
en ce nœud. Cet algorithme est détaillé en section A.2.6 ; donnons ici brièvement
son principe. Il repose sur l’opération de coupure d’un arbre de recherche τ selon
une clé x (la clé à insérer) qui partage τ en deux arbres binaires de recherche :
τ ≤x contient les clés de τ inférieures ou égales à x, et τ >x celles supérieures à x ;
l’arbre binaire de recherche ˜
τ , obtenu par insertion de x à la racine, a alors x comme
marque de la racine (évidemment !), τ ≤x comme sous-arbre gauche, et τ >x comme
sous-arbre droit (cf. la figure 6.12).
Tout ceci conduit à la définition suivante.
Définition 6.33 (L’insertion randomisée) d’une clé x dans un arbre binaire de
recherche τ consiste à insérer x à la racine avec une probabilité p(τ ) ∈ [0, 1], et
dans l’un des deux sous-arbres droit ou gauche, suivant les valeurs respectives de x
et de la marque de la racine de τ , avec la probabilité complémentaire 1 − p(τ ) ; de
plus l’insertion dans un sous-arbre se fait récursivement de façon randomisée.
Lorsque p(τ ) est nul pour tout τ , nous retrouvons l’insertion aux feuilles classique,
et lorsque p(τ ) = 1, l’insertion d’une nouvelle clé se fait à la racine.
Tournons-nous maintenant vers le cas où nous autorisons des suppressions :
l’algorithme classique, présenté en section A.2.3, remplace la clé à supprimer x,
qui est la marque de la racine d’un sous-arbre τ de l’arbre global τ , par la plus
Fig. 6.12 À gauche un arbre binaire de recherche coupé selon une valeur x ; au milieu les deux
arbres τ ≤x et τ >x obtenus par la coupure, qui contiennent respectivement les clés inférieures ou
égales à x et les clés supérieures à x ; à droite l’arbre ˜
τ obtenu après insertion de x à la racine, dont
les sous-arbres gauche et droit sont respectivement τ ≤x et τ >x
261
des performances acceptables, nous allons alors choisir d’insérer une nouvelle clé
soit dans une feuille de l’arbre complété (appelons-la f ) comme cela a été supposé
dans les sections 6.1 et 6.2, soit sur le chemin allant de la racine à f, en réorganisant
l’arbre en fonction de cette insertion. Le choix de la place où insérer sera aléatoire,
et nous verrons qu’il est possible de le faire sous une loi de probabilité choisie pour
que l’arbre binaire de recherche obtenu soit de loi Ord, i.e., que sa forme suive la
loi de l’arbre bourgeonnant.
Il nous faut d’abord indiquer comment insérer une clé à la racine d’un arbre
binaire de recherche ; il sera alors possible d’insérer une clé en tout nœud d’un
chemin de la racine vers une feuille, en l’insérant à la racine du sous-arbre enraciné
en ce nœud. Cet algorithme est détaillé en section A.2.6 ; donnons ici brièvement
son principe. Il repose sur l’opération de coupure d’un arbre de recherche τ selon
une clé x (la clé à insérer) qui partage τ en deux arbres binaires de recherche :
τ ≤x contient les clés de τ inférieures ou égales à x, et τ >x celles supérieures à x ;
l’arbre binaire de recherche ˜
τ , obtenu par insertion de x à la racine, a alors x comme
marque de la racine (évidemment !), τ ≤x comme sous-arbre gauche, et τ >x comme
sous-arbre droit (cf. la figure 6.12).
Tout ceci conduit à la définition suivante.
Définition 6.33 (L’insertion randomisée) d’une clé x dans un arbre binaire de
recherche τ consiste à insérer x à la racine avec une probabilité p(τ ) ∈ [0, 1], et
dans l’un des deux sous-arbres droit ou gauche, suivant les valeurs respectives de x
et de la marque de la racine de τ , avec la probabilité complémentaire 1 − p(τ ) ; de
plus l’insertion dans un sous-arbre se fait récursivement de façon randomisée.
Lorsque p(τ ) est nul pour tout τ , nous retrouvons l’insertion aux feuilles classique,
et lorsque p(τ ) = 1, l’insertion d’une nouvelle clé se fait à la racine.
Tournons-nous maintenant vers le cas où nous autorisons des suppressions :
l’algorithme classique, présenté en section A.2.3, remplace la clé à supprimer x,
qui est la marque de la racine d’un sous-arbre τ de l’arbre global τ , par la plus
Fig. 6.12 À gauche un arbre binaire de recherche coupé selon une valeur x ; au milieu les deux
arbres τ ≤x et τ >x obtenus par la coupure, qui contiennent respectivement les clés inférieures ou
égales à x et les clés supérieures à x ; à droite l’arbre ˜
τ obtenu après insertion de x à la racine, dont
les sous-arbres gauche et droit sont respectivement τ ≤x et τ >x