Introduction
Qu’est-ce qu’un arbre ?
Étudiés depuis longtemps par les mathématiciens avec des outils probabilistes ou
combinatoires, les arbres font partie des structures de données fondamentales en
informatique ; ils sont donc aussi sujet naturel d’étude pour les informaticiens. Dans
cet ouvrage, nous ne choisirons pas l’un ou l’autre point de vue, mais essaierons de
présenter les deux de façon complémentaire.
Qu’est-ce qu’un arbre ? Nous le définirons rigoureusement dans le chapitre 1 ;
nous en donnons deux premiers exemples dans la figure 1, et deux visions :
– au sens mathématique, c’est un graphe connexe sans cycle, parfois enraciné 1 ;
– au sens informatique, c’est une structure de données récursive : un « nœud »
appelé « racine » et ses « enfants », qui sont eux-mêmes des arbres.
Comme les arbres que les informaticiens utilisent, notamment pour stocker des
informations, ont (presque) toujours une racine, i.e. un nœud qui joue un rôle
particulier et sert d’« ancre » à l’arbre,
les arbres considérés dans ce livre sont tous enracinés.
Ainsi, l’arbre de gauche de la figure 1 – nous employons, pour dessiner un arbre,
la convention de mettre la racine en haut ; l’arbre « pousse » donc vers le bas
– a une racine, qui a elle-même trois enfants ; en lisant de gauche à droite, les
1 Tout livre sur les graphes fournit les définitions de base sur le sujet, en particulier celle d’un arbre ;
nous y renvoyons la lectrice intéressée, et ne poursuivons pas cette approche ici.
xv