Quizz - construire un arbre à partir d’une liste (et vice-versa)

L’objet de ce quizz est un petit problème d’algorithmique, qui nous a occupé un bon moment pendant que nous mettions en place la table des matières automatique dans le wiki collaboratif. Voici comment le problème se présente.

Vous disposez d’un document HTML, pour lequel vous souhaitez construire une table des matières. La première chose à faire est bien entendu d’extraire les titres, disons simplement H1, H2 et H3. Vous sortez votre parser de HTML préféré, et vous le réglez pour qu’il vous extraie la liste dfe ces titres, dans l’ordre d’apparition bien sûr, ce qui n’était pas une mince affaire avec notre librairie HPricot. Après avoir inséré un élément « racine » en tête de liste, on obtient la liste suivante :

[ ( 0 , "root"),
  ( 1 , "Titre 1"),
  ( 2 , "Titre 1.1"),
  ( 2 , "Titre 1.2"),
  ( 3 , "Titre 1.2.1"),
  ( 2 , "Titre 1.3"),
  ( 1 , "Titre 2") ]

Le rôle de l’élément racine est simplement de garantir que tous les éléments de la queue de la liste sont d’un niveau inférieur, ce qui fait de cette tête de liste un candidat idéal pour constituer la racine de l’arbre. Ensuite viennent les vrais titres, il s’agit des couples ( niveau de titre , texte du titre ). Bien qu’elle reflète une hiérarchie, cette liste est terriblement plate. Ainsi l’a voulu le HTML. Or justement, il se trouve que nous aurions bien besoin de manipuler cette structure de donnée sous forme d’arbre, comme illustré ci-dessous.

root --- Titre 1
      |  |- Titre 1.1
      |  |- Titre 1.2
      |  |   \- Titre 1.2.1
      |  \- Titre 1.3
      \- Titre 2

Une telle structure nous permettrait en particulier de générer la table des matières de façon récursive, ce qui ferait très plaisir à notre responsable CSS.

Le problème peut donc être énoncé ainsi : « À partir d’une structure de données séquentielle mentionnant un niveau de profondeur, comment construire une structure de donnée arborescente reflétant la hiérarchie entre les éléments ?».

Nous appelerons cette fonction list2tree. Comme apéritif, je vous invite à spécifier les types de données concernés :

• couple ( profondeur , nom )
• liste plate des éléments
• arbre récursif des éléments
• list2tree
• tree2list

Pour l’entrée, je vous propose de définir la fonction tree2list, inverse de notre problème, c’est à dire celle qui part de l’arbre pour produire la liste plate.

Enfin, vous pourrez attaquer le plat de résistance, qui est la définition de la fonction list2tree qui transforme la liste en arbre.

Le dessert est de vérifier sur quelques exemples que la composition de ces deux fonctions est une identité.

tree2list o list2tree == id

À vous de jouer.

Notre solution (mise en ligne le Lundi 11 Octobre 2010)

Il est temps de partager notre solution, basée sur un traitement récursif de la liste, et n’utilisant pas de variable. Voici la description de la procédure :

• on prend d’un côté la tête de la liste, de l’autre sa queue,
• on lit le niveau de la tête,
• on coupe la queue en deux, au point où le niveau devient inférieur ou égal au niveau de la tête. La première partie constituera les enfants, la seconde partie les frères,
• on construit l’arbre avec la tête et les enfants transformés à leur tour en arbres (récursion), puis on traite les frères (récursion).

En Haskell, la fonction qui coupe une liste en deux au point d’invalidation d’un prédicat s’appelle span, elle fait partie du Prelude. Nous pouvons donc facilement écrire notre fonction :

-- définition du type abstrait de l'arbre récursif à N fils
data TreeN a = TreeN a [TreeN a] deriving Show 

list2tree :: [(Integer, String)] -> TreeN String
list2tree ((rl,rt):es) = TreeN rt (list2tree' es rl) where
   list2tree' [] _ = []
   list2tree' ((level,text):xs) cl =
     let (children_list,brothers_list) = span (\ (l,_) -> level < l) xs
         children = list2tree' children_list (cl + 1)
         brothers = list2tree' brothers_list cl in
     (TreeN text children) : brothers

AtikTeam étant codé en Ruby On Rails, nous avons traduit notre fonction. En Ruby, il n’y a pas de véritable type Liste, et la fonction span ne fait pas partie de la librairie standard, nous en avons donc fait une implémentation, en ajoutant quelques méthodes de listes pour Array.

class Array
  class NoHead; end
  
  def head; empty? ? NoHead : first; end
  def tail; size > 1 ? self[1..-1] : []; end

  def span(&block)
    if empty? then [[],[]]
    elsif (yield head) then
      a,b = tail.span(&block)
      [a.unshift(head),b]
    else [[], self]
    end
  end
end

Ce qui nous a permis ensuite de définir notre fonction list2tree.

def list_to_tree(list, level)
  return [] if list.nil? or list.empty?
  pl,pa,pc = list.head
  subtrees, rest = list.tail.span{|l,a,c| pl<l}
  [TreeN.new(list.head, list_to_tree(subtrees,level+1))] + list_to_tree(rest, level)
end

Et voila pour notre proposition. Vos solutions sont toujours les bienvenues dans les commentaires !