Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 27 Novembre 2007

Le profil des arbres digitaux

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr