Des arbres et des couleurs

N’oubliez pas d’aller consulter la documentation des modules Data.List, Data.Maybe, Test.QuickCheck, etc. dès que vous vous doutez qu’elle peut vous apporter une aide.

Arbres binaires

Commençons par choisir leur type. Comme nous allons vouloir mettre des couleurs sur les nœuds, ces arbres seront paramétrés par deux types, un type de couleur et un type de valeur1.

  1. Déclarez un type Arbre pour les arbres binaires. Ce type sera paramétré par le type des couleurs et le type des valeurs des nœuds.

    Votre déclaration pourra donc ressembler à :

    Les feuilles ne porteront pas de valeur, seuls les nœuds en auront.

  2. Définissez une fonction mapArbre pour votre type Arbre.
    Comme chaque nœud porte une couleur et une valeur, votre fonction mapArbre pourra être paramétrée par deux fonctions, une calculant la nouvelle couleur, l’autre la nouvelle valeur.

  3. Définissez les fonctions qui calculent la hauteur (nombre maximal de nœuds entre une feuille et la racine) et la taille (nombre total de nœuds) d’un arbre.

Les deux fonctions hauteur et taille doivent avoir un code très similaire : il est donc possible de définir une fonction plus générique afin d’éviter la duplication de code.

  1. Définissez une fonction générique dimension telle que hauteur et taille puissent être redéfinies comme des applications partielles de dimension.

On appelle peigne à gauche un arbre dont tous les sous-arbres droits sont des feuilles. Notez qu’un peigne est équivalent à une liste.

Peigne avec trois nœuds
Peigne avec trois nœuds
  1. Définissez une fonction peigneGauche :: [(c,a)] -> Arbre c a qui prend une liste de paires de couleur et valeur et crée le peigne à gauche correspondant.

Vous allez utiliser quickCheck pour vérifier quelques propriétés de votre code. Pour cela, vous pourrez :

Cela vous permettra d’écrire quelques fonctions qui vérifient une propriété que votre code doit respecter et faire vérifier qu’elle est satisfaite sur une série de cas générés aléatoirement par QuickCheck.

  1. Ajouter la fonction suivante à votre code source :

    Que vérifie-t-elle ?

    Vérifiez avec QuickCheck qu’elle est satisfaite2 en appelant quickCheck :

    ghci> quickCheck prop_hauteurPeigne
    +++ OK, passed 100 tests.

    Si QuickCheck trouve un cas de test sur lequel la propriété n’est pas vraie, il vous donne le cas qu’il a trouvé :

    ghci> quickCheck prop_hauteurPeigne
    *** Failed! Falsifiable (after 1 test):
    []

    Vous pouvez alors regarder le peigneGauche [] et comprendre pourquoi.

  2. Testez quelques propriétés sur taille, mapArbre, etc.

On appelle arbre binaire complet (ou parfait) un arbre dont toutes les feuilles sont à la même distance de la racine. Ainsi l’arbre complet de hauteur 0 est simplement une feuille. Les arbres complets de hauteur 1, 2, 3 et 4 sont les suivants (où les feuilles ne sont pas explicitées) :

Arbre complet de hauteur 1
Arbre complet de hauteur 1
Arbre complet de hauteur 2
Arbre complet de hauteur 2
Arbre complet de hauteur 3
Arbre complet de hauteur 3
Arbre complet de hauteur 4
Arbre complet de hauteur 4
  1. Définissez une fonction estComplet :: Arbre c a -> Bool qui vaut vrai si et seulement si son argument est un arbre complet.

Votre fonction estComplet doit effectuer un parcours de l’arbre pour déterminer s’il est complet. Elle doit donc partager une large partie du code de taille et hauteur.

  1. Est-il possible de définir estComplet comme une application partielle de dimension ? Si ça n’est pas le cas, définissez une fonction assez générique pour que taille et hauteur en soient des applications partielles et estComplet le soit presque (il sera nécessaire de faire un dernier traitement sur le résultat pour définir estComplet).

  2. Quels sont les peignes à gauche complets ? Pouvez-vous utiliser QuickCheck pour les trouver ?

Les exemples ci-dessus ont été générés par une fonction complet :: Int -> [(c, a)] -> Arbre c a qui prend en argument une hauteur et une liste de paires de couleur et valeur.

Un point auquel il faut faire attention est de savoir dans quel ordre vous utilisez les couleurs et étiquettes. Par exemple l’arbre de hauteur 2 ci-dessus a été généré par complet 2 [((),'a'),((),'b'),((),'c')]. Vous veillerez à utiliser les valeurs dans le même ordre : vous créerez le sous-arbre gauche avant le nœud central, avant le sous-arbre droit.

  1. Définissez la fonction complet.

    Combien de nœuds et de feuilles a l’arbre complet de hauteur n ? Concluez-en qu’il n’est pas raisonnable de construire des arbres complets de hauteur 20 ou plus ! Il est sans doute même pertinent de se limiter à une profondeur 17 au maximum. Prenez ça en compte en écrivant quelques tests avec QuickCheck.

Notez au passage que nous avons utilisé () pour donner une valeur sans grand intérêt comme couleur : il s’agit du 0-uplet, très utile comme bouche-trou (quand il faut bien mettre quelque chose tout en exprimant que la valeur est sans intérêt).

Pour utiliser complet, il vous faut fournir une liste des étiquettes et des couleurs. Pour des arbres un peu grands, c’est rapidement fastidieux.

  1. Trouvez la fonction de type a -> [a] qui vous donne une liste contenant une infinité de fois son argument.

    Redéfinissez cette fonction en utilisant iterate.

  2. En utilisant le fait que ['a'..] est la liste de tous les caractères unicode à partir de 'a', créez la liste contenant [((),'a'), ((),'b'), ...].

  3. Définissez la fonction aplatit :: Arbre c a -> [(c, a)] qui calcule la liste des paires couleur-valeur présentes dans les nœuds de l’arbre.

    Vous veillerez (et testerez avec QuickCheck) à ce que l’ordre dans la liste corresponde à l’ordre indiqué pour l’arbre complet. C’est-à-dire que, pour l’arbre complet de hauteur 4 ci-dessus :

  4. Définissez une fonction element :: Eq a => a -> Arbre c a -> Bool qui calcule si un élément de valeur donnée est présent dans l’arbre.

    Vous pourrez vérifier des propriétés de cette fonction, par exemple exprimées par rapport à la version aplatie de l’arbre.

Affichage des arbres

Nous allons utiliser graphviz pour obtenir un rendu visuel des arbres construits. Sa syntaxe de description des graphes est très simple. Par exemple, l’arbre complet de hauteur 3 est décrit par les données suivantes :

/* Entête */
digraph "complet3" {
    node [fontname="DejaVu-Sans", shape=circle]

    /* Liste des nœuds */
    a
    b
    c
    d
    e
    f
    g

    /* Liste des arcs */
    d -> b
    d -> f
    b -> a
    b -> c
    f -> e
    f -> g
}

que le programme dot convertit en une image. Par exemple, si vous mettez la description précédente dans un fichier arbre.dot et tapez dot -Txlib arbre.dot, dot vous affichera une fenêtre avec le dessin de l’arbre. dot -Tpng arbre.dot > arbre.png vous donnera un fichier image.

L’indentation n’est pas requise, vous pourrez vous passer de la générer. L’idée est donc juste de générer la liste des nœuds (dans l’ordre déjà choisi pour aplatit : l’ordre a un impact sur le placement des nœuds, les nœuds les plus à gauche doivent être déclarés avant les nœuds les plus à droite).

Comme les nœuds ont des couleurs3, vous pouvez utiliser la syntaxe :

a [color=red, fontcolor=red]

pour faire un nœud rouge.

Attention, les fonctions que nous proposons ici supposent que les nœuds ont des valeurs uniques qui peuvent être utilisées comme identifiants. En effet, deux nœuds d’un arbre ayant la même valeur seraient fusionnés dans le rendu graphviz.

  1. Définissez une petite fonction noeud :: (c -> String) -> (a -> String) -> (c,a) -> String qui transforme une entrée de la liste aplatie d’un arbre en une ligne de déclaration du nœud en utilisant une fonction qui génère une String pour la couleur et une autre fonction qui génère une String pour la valeur.

  2. Définissez une fonction arcs :: Arbre c a -> [(a,a)] qui produit la liste de tous les arcs de l’arbre.

  3. Définissez une petite fonction arc :: (a -> String) -> (a,a) -> String qui transforme un arc de la liste précédente en une ligne graphviz en utilisant une fonction qui génère une String pour une valeur.

  4. Finalement, définissez une fonction dotise :: String -> (c -> String) -> (a -> String) -> Arbre c a -> String qui prend en argument :

    • le nom de l’arbre produit,
    • une fonction de conversion pour les couleurs,
    • une fonction de conversion pour les valeurs,
    • un arbre,

    et calcule la chaîne de caractères représentant l’arbre.

    Cette fonction pourra avantageusement utiliser la fonction unlines.

Enfin de la couleur… !

Un arbre binaire de recherche est un arbre contenant des valeurs ordonnées de sorte que la valeur d’un nœud est supérieure à la valeur de tous les nœuds de son sous-arbre gauche, et inférieure à la valeur de tous les nœuds de son sous-arbre droit.

  1. Définissez une fonction elementR qui cherche une valeur dans un arbre binaire de recherche. Au lieu de regarder « taille » nœuds, elle regardera au plus « hauteur » nœuds.

Si l’arbre est complet, la hauteur est un logarithme de la taille, ce qui rend la recherche d’un élément particulièrement efficace. Mais il est dur d’obtenir un arbre complet par des ajouts successifs. Les arbres sont dits équilibrés quand ils assurent une recherche efficace même s’ils ne sont pas totalement complets.

Il existe un type d’arbres binaires de recherche qui s’implémentent de façon particulièrement élégante en utilisant du filtrage de motifs : les arbres rouges et noirs. Depuis quelques années, ces arbres sont utilisés dans l’implémentation de HashMap d’OpenJDK afin d’améliorer les performances de la structure de donnée (dans le pire cas) mais aussi de résister aux attaques exploitant les collisions de hash (voir les explications de l’implémentation).

Les propriétés d’un arbre rouge et noir sont les suivantes :

Ces propriétés garantissent que le plus long chemin racine-feuille (qui aurait une alternance rouge-noir) ne pourrait pas être plus que deux fois plus long que le plus court (qui n’aurait que des nœuds noirs).

L’insertion d’une valeur fonctionne de la façon suivante :

Tout repose sur la technique de rééquilibrage, quand on a un nœud rouge qui a un fils rouge. Plus concrètement, il suffit de rééquilibrer les arbres qui ont une des 4 formes suivantes :

Arbres déséquilibrés
Arbres déséquilibrés

(où « a », « b », « c » et « d » sont des sous-arbres quelconques) en les transformant en l’arbre :

Arbre rééquilibré
Arbre rééquilibré

Dans tous les autres cas, la fonction de rééquilibrage laisse l’arbre inchangé.

  1. Déclarez un type Couleur à deux valeurs, correspondant soit au rouge, soit au noir.

    Créez un synonyme de type ArbreRN, en utilisant Arbre et Couleur, de sorte que ArbreRN Char soit le type des arbres rouges et noirs contenant des Char comme valeurs.

  2. Définissez la fonction de rééquilibrage equilibre :: ArbreRN a -> ArbreRN a4.

    Cette fonction se définit très simplement en filtrant les motifs possibles. Vous pourrez choisir des constructeurs pour vos arbres et vos couleurs de sorte que les motifs soient plus concis (j’ai utilisé les constructeurs R et N pour les couleurs, par exemple…).

  3. Définissez la fonction d’insertion d’une valeur dans un arbre rouge et noir.

  4. Identifiez et vérifiez avec QuickCheck quelques propriétés des arbres rouges et noirs.

    En particulier, quelle propriété pouvez-vous définir sur les aplatissements d’arbres rouges et noirs ?

… et un peu d’animation

Créez un fichier, par exemple arbre.dot, contenant :

digraph "arbre" { }

et lancez dot -Txlib arbre.dot. dot -Txlib a le bon goût (normalement…) de surveiller les changements du fichier qu’il affiche. Nous allons donc pouvoir visualiser les ajouts des valeurs à l’arbre au fur et à mesure. Le but est d’obtenir une visualisation ressemblant aux figures suivantes. Vous pouvez aussi étudier les étapes de ces constructions sans animation : ordres alphabétique et aléatoire.

Ajouts successifs de ['a'..'z']
Ajouts successifs de ['a'..'z']
Ajouts successifs de "gcfxieqzrujlmdoywnbakhpvst"
Ajouts successifs de "gcfxieqzrujlmdoywnbakhpvst"
  1. Définissez une fonction arbresDot :: [Char] -> [String] qui, pour une liste de caractères, retourne une liste des chaînes produites par dotise. À la position i de la liste résultat, il y aura ainsi la description au format graphviz de l’arbre obtenu par les ajouts successifs des caractères aux positions 0 à i − 1 de la liste passée en argument.

Ajoutez finalement le petit main magique suivant :

import Control.Concurrent (threadDelay)

main = mapM_ ecrit arbres
    where ecrit a = do writeFile "arbre.dot" a
                       threadDelay 1000000
          arbres  = arbresDot "gcfxieqzrujlmdoywnbakhpvst"

et runghc arbres.hs (si votre source s’appelle arbres.hs) devrait modifier le fichier arbre.dot toutes les secondes.

Extensions possibles

Deux idées d’extensions possibles.

  1. L’implémentation suggérée ci-dessus suppose que le type des valeurs soit ordonné (de la classe Ord). Faites une version des fonctions d’insertion et de test d’appartenance prenant une fonction d’ordre en argument.

  2. Les garanties de complexité des arbres rouges et noirs en font une bonne base pour implémenter un dictionnaire. Faites-en une implémentation.


Référence : Chris Okasaki, Purely functional data structures. Cambridge University Press 1999.


  1. Nous pourrions bien entendu utiliser un type d’arbre paramétré par un seul type, de valeur, et utiliser (Couleur,Valeur) comme type de valeur pour les versions coloriées. Nous avons ici choisi de séparer explicitement les deux pour alléger l’écriture des fonctions qui traitent les nœuds suivant leur couleur.

  2. Satisfaite sur les cas aléatoires : comme toujours en test, on ne trouve que des erreurs, on n’obtient aucune preuve que le résultat sera correct dans tous les cas.

  3. pas encore très utilisées dans cet énoncé, il est vrai…

  4. Ou, légèrement plus efficace, une fonction equilibre :: Couleur -> a -> ArbreRN a -> ArbreRN a -> ArbreRN a c’est-à-dire ayant la même signature que votre constructeur de nœud mais évitant de construire un arbre déséquilibré juste pour le rééquilibrer.