3.2 Recherche de clés
65
Fig. 3.4 Un arbre binaire de recherche τ et son complété ˜
τ . La taille de τ est |τ | = 7, son niveau
de saturation s(τ ) = 1 et sa hauteur h(τ ) = 3. Sa longueur de cheminement totale est lc(τ ) = 11,
et c’est aussi la longueur de cheminement interne de ˜
τ , dont la longueur de cheminement externe
est lce( ˜
τ ) = 25 ; la longueur de cheminement totale de ˜
τ vaut 11 + 25 = 36. La profondeur
d’insertion de la clé −1 est d(−1, τ ) = 3, et celle d’une nouvelle occurrence de la clé 4 est
d(4, τ ) = 3
en parcourant un unique chemin dans l’arbre, qui part de la racine et chemine
vers ses descendants en éliminant à chaque niveau, grâce à la comparaison avec
la clé à la racine du sous-arbre, le sous-arbre droit ou le sous-arbre gauche. Les
différents coûts algorithmiques relatifs à ces opérations s’expriment en fonction des
paramètres d’arbre, en prenant habituellement pour fonction de coût le nombre de
comparaisons de clés. Cependant, certains travaux prennent en compte le nombre
de comparaisons de bits effectuées pour comparer les clés, considérées en tant
que chaînes de caractères, cf. les résultats de Fill et Janson ou l’article de Fill
et al. [77, 246].
Regardons ces différents coûts pour l’exemple donné en figure 3.4 : les clés 0, 4
et 10 ont été insérées à une profondeur 2, et il faut 3 comparaisons pour retrouver
chacune de ces clés ; la clé 6 a été insérée à une profondeur 3 et il faut 4
comparaisons pour la retrouver. De façon générale, la première comparaison se
faisant avec la clé à la racine qui est à profondeur 0, le nombre de comparaisons
pour retrouver une clé présente dans l’arbre τ est égal à 1 + sa profondeur.
Les paramètres intéressants sont essentiellement, pour un arbre binaire de
recherche fixé τ , la taille |τ |, les longueurs de cheminement interne lci(τ ), externe
lce(τ ) et totale lc(τ ) = lci(τ ) + lce(τ ), la hauteur h(τ ), le niveau de saturation s(τ )
et la profondeur d’insertion d(α, τ ) d’une nouvelle clé α dans τ , i.e., la profondeur
du nœud dans lequel se trouvera la clé après son insertion dans l’arbre. Nous
allons voir comment tous ces paramètres servent à exprimer les coûts des différents
algorithmes.
Pour simplifier la présentation, notons ˜
τ l’arbre complet obtenu en ajoutant à τ
les feuilles correspondant aux possibilités d’insertion, cf. un exemple d’arbre τ et
recherche randomisés analysés en section 6.5. L’algorithme pour l’insertion à la racine est donné
en annexe A.2.4.
65
Fig. 3.4 Un arbre binaire de recherche τ et son complété ˜
τ . La taille de τ est |τ | = 7, son niveau
de saturation s(τ ) = 1 et sa hauteur h(τ ) = 3. Sa longueur de cheminement totale est lc(τ ) = 11,
et c’est aussi la longueur de cheminement interne de ˜
τ , dont la longueur de cheminement externe
est lce( ˜
τ ) = 25 ; la longueur de cheminement totale de ˜
τ vaut 11 + 25 = 36. La profondeur
d’insertion de la clé −1 est d(−1, τ ) = 3, et celle d’une nouvelle occurrence de la clé 4 est
d(4, τ ) = 3
en parcourant un unique chemin dans l’arbre, qui part de la racine et chemine
vers ses descendants en éliminant à chaque niveau, grâce à la comparaison avec
la clé à la racine du sous-arbre, le sous-arbre droit ou le sous-arbre gauche. Les
différents coûts algorithmiques relatifs à ces opérations s’expriment en fonction des
paramètres d’arbre, en prenant habituellement pour fonction de coût le nombre de
comparaisons de clés. Cependant, certains travaux prennent en compte le nombre
de comparaisons de bits effectuées pour comparer les clés, considérées en tant
que chaînes de caractères, cf. les résultats de Fill et Janson ou l’article de Fill
et al. [77, 246].
Regardons ces différents coûts pour l’exemple donné en figure 3.4 : les clés 0, 4
et 10 ont été insérées à une profondeur 2, et il faut 3 comparaisons pour retrouver
chacune de ces clés ; la clé 6 a été insérée à une profondeur 3 et il faut 4
comparaisons pour la retrouver. De façon générale, la première comparaison se
faisant avec la clé à la racine qui est à profondeur 0, le nombre de comparaisons
pour retrouver une clé présente dans l’arbre τ est égal à 1 + sa profondeur.
Les paramètres intéressants sont essentiellement, pour un arbre binaire de
recherche fixé τ , la taille |τ |, les longueurs de cheminement interne lci(τ ), externe
lce(τ ) et totale lc(τ ) = lci(τ ) + lce(τ ), la hauteur h(τ ), le niveau de saturation s(τ )
et la profondeur d’insertion d(α, τ ) d’une nouvelle clé α dans τ , i.e., la profondeur
du nœud dans lequel se trouvera la clé après son insertion dans l’arbre. Nous
allons voir comment tous ces paramètres servent à exprimer les coûts des différents
algorithmes.
Pour simplifier la présentation, notons ˜
τ l’arbre complet obtenu en ajoutant à τ
les feuilles correspondant aux possibilités d’insertion, cf. un exemple d’arbre τ et
recherche randomisés analysés en section 6.5. L’algorithme pour l’insertion à la racine est donné
en annexe A.2.4.