1.3 Paramètres d’arbres
37
Fig. 1.36 Du haut vers le bas : un arbre lexicographique, un trie et un arbre digital de recherche.
Les trois structures sont construites sur les mots (en anglais) constituant la dernière phrase du
roman Moby Dick de Melville (insérés dans l’ordre de la phrase, ce qui n’influe que dans le cas
de l’arbre digital de recherche) : “The Drama’s Done. Why then here does any one step forth ?
- Because one did survive the wreck.”. Dans le trie, les nœuds qui n’ont qu’un enfant et qui ne
seraient pas présents dans l’arbre PATRICIA sont encerclés. Une lettre terminale ‘†’ est ajouté à la
fin de chaque mot. Les arêtes au lieu des nœuds portent les étiquettes pour plus de clarté
nœud, de sa génération, de sa profondeur dans l’arbre, ou de la longueur du mot
associé à ce nœud. La racine est à la génération 0. Pour un arbre planaire dont les
nœuds sont canoniquement numérotés et pour tout entier n, la n-ième génération
est l’ensemble des nœuds dont le numéro, au sens de la définition 1.1, est de
longueur n.
– La longueur de cheminement d’un arbre τ est la somme des niveaux des nœuds :
lc(τ ) =
u∈τ |u|, où |u| est la longueur du mot u, i.e., la profondeur (ou le
niveau) du nœud correspondant dans l’arbre. Deux variantes sont les longueurs de
cheminement interne lci(τ ) =
u∈τ \∂τ |u| et externe lce(τ ) =
u∈∂τ |u|, qui
37
Fig. 1.36 Du haut vers le bas : un arbre lexicographique, un trie et un arbre digital de recherche.
Les trois structures sont construites sur les mots (en anglais) constituant la dernière phrase du
roman Moby Dick de Melville (insérés dans l’ordre de la phrase, ce qui n’influe que dans le cas
de l’arbre digital de recherche) : “The Drama’s Done. Why then here does any one step forth ?
- Because one did survive the wreck.”. Dans le trie, les nœuds qui n’ont qu’un enfant et qui ne
seraient pas présents dans l’arbre PATRICIA sont encerclés. Une lettre terminale ‘†’ est ajouté à la
fin de chaque mot. Les arêtes au lieu des nœuds portent les étiquettes pour plus de clarté
nœud, de sa génération, de sa profondeur dans l’arbre, ou de la longueur du mot
associé à ce nœud. La racine est à la génération 0. Pour un arbre planaire dont les
nœuds sont canoniquement numérotés et pour tout entier n, la n-ième génération
est l’ensemble des nœuds dont le numéro, au sens de la définition 1.1, est de
longueur n.
– La longueur de cheminement d’un arbre τ est la somme des niveaux des nœuds :
lc(τ ) =
u∈τ |u|, où |u| est la longueur du mot u, i.e., la profondeur (ou le
niveau) du nœud correspondant dans l’arbre. Deux variantes sont les longueurs de
cheminement interne lci(τ ) =
u∈τ \∂τ |u| et externe lce(τ ) =
u∈∂τ |u|, qui