66
3 Arbres, algorithmes et données
de son complété ˜
τ en figure 3.4. L’arbre ˜
τ a |τ | + 1 feuilles, ses nœuds internes sont
tous les nœuds de l’arbre τ , et lce( ˜
τ) = 2 |τ | + lc(τ ).
– Le coût d’insertion aux feuilles d’une nouvelle clé α dans une feuille de τ , mesuré
en nombre de comparaisons de clés, est exactement d(α, τ ). Au mieux, ce coût
est égal au niveau de saturation s(τ ) ; au pire, il est égal à la hauteur h(τ ).
– Le coût de la recherche sans succès d’une clé α dans τ est aussi d(α, τ ). En
effet, la recherche d’une clé qui ne se trouve pas dans l’arbre τ conduit à une
feuille de l’arbre complété ˜
τ , celle où serait insérée la clé. Le coût cumulé d’une
recherche sur toutes les positions possibles est alors exactement la somme des
profondeurs des |τ | + 1 feuilles de ˜
τ , c’est-à-dire sa longueur de cheminement
externe lce( ˜
τ ). Si nous prenons la moyenne du nombre de comparaisons de clés,
en supposant toutes les positions possibles équiprobables, ce coût moyen d’une
recherche vaine est
lce( ˜
τ )
|τ | + 1
=
lc(τ )
|τ | + 1
+ 2 −
2
|τ | + 1
.
– Le coût de la recherche avec succès de la première occurrence 4 d’une clé α dans
un arbre τ est égal à la profondeur du nœud qui la contient. Le coût moyen d’une
recherche avec succès, lorsque toutes les clés présentes dans l’arbre ont même
probabilité d’être recherchées et sont toutes distinctes, est
lc(τ )
|τ | .
– Le coût de construction d’un arbre binaire de recherche τ par insertion aux
feuilles n’est autre que la longueur de cheminement lc(τ ).
– Le coût de la suppression d’une clé x présente dans l’arbre τ se décline en deux
parties 5 : tout d’abord, trouver la clé à supprimer (ou sa première occurrence si
elle est répétée) – c’est l’algorithme Suppression de l’annexe A.2.3, dont le
coût est celui de la recherche avec succès de x – puis faire effectivement cette
suppression – c’est l’algorithme Suppression-Racine de la même section.
Appelons u le nœud contenant l’occurrence de x à supprimer, et notons τ u
le sous-arbre de τ ayant pour racine u. Si nous cherchons à préciser le coût
de suppression à la racine dans τ u , l’examen de l’algorithme montre qu’il est
essentiellement déterminé par la recherche de la plus grande clé du sous-arbre
gauche de τ u , i.e., par la longueur de la branche droite de ce sous-arbre. Il pourra
donc être intéressant de déterminer la distribution de cette longueur, conditionnée
par la taille de τ u .
Les lois de probabilité des différents paramètres sur les arbres binaires de recherche, et donc des coûts des diverses opérations de recherche et mise à jour dans
4 Les différentes occurrences d’une même clé se trouvent toutes sur un même chemin de la racine
vers une feuille (mais ne sont pas nécessairement consécutives) et il est possible de les ordonner
par niveau croissant ; la « première » occurrence d’une clé est alors celle de niveau minimal.
5 Nous nous limitons ici à l’algorithme standard de recherche de la clé à supprimer puis suppression
à la racine ; comme pour l’insertion, il existe une variante randomisée, présentée en annexe A.2.5
et analysée en section 6.5.
3 Arbres, algorithmes et données
de son complété ˜
τ en figure 3.4. L’arbre ˜
τ a |τ | + 1 feuilles, ses nœuds internes sont
tous les nœuds de l’arbre τ , et lce( ˜
τ) = 2 |τ | + lc(τ ).
– Le coût d’insertion aux feuilles d’une nouvelle clé α dans une feuille de τ , mesuré
en nombre de comparaisons de clés, est exactement d(α, τ ). Au mieux, ce coût
est égal au niveau de saturation s(τ ) ; au pire, il est égal à la hauteur h(τ ).
– Le coût de la recherche sans succès d’une clé α dans τ est aussi d(α, τ ). En
effet, la recherche d’une clé qui ne se trouve pas dans l’arbre τ conduit à une
feuille de l’arbre complété ˜
τ , celle où serait insérée la clé. Le coût cumulé d’une
recherche sur toutes les positions possibles est alors exactement la somme des
profondeurs des |τ | + 1 feuilles de ˜
τ , c’est-à-dire sa longueur de cheminement
externe lce( ˜
τ ). Si nous prenons la moyenne du nombre de comparaisons de clés,
en supposant toutes les positions possibles équiprobables, ce coût moyen d’une
recherche vaine est
lce( ˜
τ )
|τ | + 1
=
lc(τ )
|τ | + 1
+ 2 −
2
|τ | + 1
.
– Le coût de la recherche avec succès de la première occurrence 4 d’une clé α dans
un arbre τ est égal à la profondeur du nœud qui la contient. Le coût moyen d’une
recherche avec succès, lorsque toutes les clés présentes dans l’arbre ont même
probabilité d’être recherchées et sont toutes distinctes, est
lc(τ )
|τ | .
– Le coût de construction d’un arbre binaire de recherche τ par insertion aux
feuilles n’est autre que la longueur de cheminement lc(τ ).
– Le coût de la suppression d’une clé x présente dans l’arbre τ se décline en deux
parties 5 : tout d’abord, trouver la clé à supprimer (ou sa première occurrence si
elle est répétée) – c’est l’algorithme Suppression de l’annexe A.2.3, dont le
coût est celui de la recherche avec succès de x – puis faire effectivement cette
suppression – c’est l’algorithme Suppression-Racine de la même section.
Appelons u le nœud contenant l’occurrence de x à supprimer, et notons τ u
le sous-arbre de τ ayant pour racine u. Si nous cherchons à préciser le coût
de suppression à la racine dans τ u , l’examen de l’algorithme montre qu’il est
essentiellement déterminé par la recherche de la plus grande clé du sous-arbre
gauche de τ u , i.e., par la longueur de la branche droite de ce sous-arbre. Il pourra
donc être intéressant de déterminer la distribution de cette longueur, conditionnée
par la taille de τ u .
Les lois de probabilité des différents paramètres sur les arbres binaires de recherche, et donc des coûts des diverses opérations de recherche et mise à jour dans
4 Les différentes occurrences d’une même clé se trouvent toutes sur un même chemin de la racine
vers une feuille (mais ne sont pas nécessairement consécutives) et il est possible de les ordonner
par niveau croissant ; la « première » occurrence d’une clé est alors celle de niveau minimal.
5 Nous nous limitons ici à l’algorithme standard de recherche de la clé à supprimer puis suppression
à la racine ; comme pour l’insertion, il existe une variante randomisée, présentée en annexe A.2.5
et analysée en section 6.5.