Nicolas Broutin (INRIA)

(en collaboration avec L. Devroye)

Il est possible de distinguer deux régions dans les arbres digitaux : la majorité des noeuds forme un coeur dense duquel pendent des arbres longilignes, les spaghettis. Cette distinction peut-être vue comme le chaînon manquant entre les arbres digitaux de recherche et les tries puisqu’elle explique les similarités entre leurs profils, mais aussi les différences. Ce nouvel éclairage des arbres digitaux est à l’origine de l’étude de la hauteur des tries hybrides, des structures de données digitales plus complexes, et en particulier des TST de Bentley et Sedgewick.