Arbre binaire de recherche

Instructions

Insère et recherche des nombres dans un arbre binaire.

Quand on doit représenter des données triées, un tableau n'est pas une bonne structure de données.

Imaginons que l'on ait le tableau [1, 3, 4, 5] et qu'on y ajoute 2 : il devient [1, 3, 4, 5, 2]. Il faut alors trier tout le tableau à nouveau ! On peut améliorer cela en se rendant compte qu'il suffit de faire de la place pour le nouvel élément [1, nil, 3, 4, 5], puis d'ajouter l'élément dans l'espace ainsi créé. Mais cela nous oblige quand même à décaler de nombreux éléments d'une position.

Les arbres binaires de recherche, eux, peuvent travailler sur des données triées bien plus efficacement.

Un arbre binaire de recherche se compose d'une série de nœuds reliés entre eux. Chaque nœud contient une donnée (par exemple le nombre 3), une variable nommée left et une variable nommée right. Les variables left et right pointent vers nil, ou vers d'autres nœuds. Comme ces autres nœuds ont eux-mêmes d'autres nœuds sous eux, on dit que les variables left et right pointent vers des sous-arbres. Toutes les données du sous-arbre gauche sont inférieures ou égales à la donnée du nœud courant, et toutes les données du sous-arbre droit sont supérieures à la donnée du nœud courant.

Par exemple, si on avait un nœud contenant la donnée 4 et qu'on y ajoutait la donnée 2, notre arbre ressemblerait à ceci :

  4
 /
2

Si on ajoutait ensuite 6, il ressemblerait à ceci :

  4
 / \
2   6

Si on ajoutait ensuite 3, il ressemblerait à ceci

   4
 /   \
2     6
 \
  3

Et si on ajoutait ensuite 1, 5 et 7, il ressemblerait à ceci

      4
    /   \
   /     \
  2       6
 / \     / \
1   3   5   7

Indices

Pour terminer cet exercice, tu dois créer le type de données BST, avec des instances Eq et Show, et implémenter les fonctions :

• bstLeft
• bstRight
• bstValue
• empty
• fromList
• insert
• singleton
• toList

Tu trouveras une déclaration de données factice et des signatures de type déjà en place, mais c'est à toi de définir les fonctions et de créer un type de données, un newtype ou un synonyme de type qui a du sens.