Arbre binaire de recherche

Instructions

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

Quand on a besoin de 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 que l'on y ajoute 2, ce qui donne [1, 3, 4, 5, 2]. Il faut maintenant trier à nouveau tout le tableau ! On peut faire mieux en remarquant qu'il suffit de faire de la place pour le nouvel élément [1, nil, 3, 4, 5], puis d'y insérer l'élément. Mais cela oblige quand même à décaler d'une position de nombreux éléments.

Les arbres binaires de recherche, en revanche, permettent de traiter des données triées bien plus efficacement.

Un arbre binaire de recherche est constitué 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 en dessous d'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 aux données du nœud courant, et toutes les données du sous-arbre droit sont supérieures aux données du nœud courant.

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

      4
     /
    2

Si on ajoute ensuite 6, il ressemblerait à ceci :

      4
     / \
    2   6

Si on ajoute ensuite 3, il ressemblerait à ceci

       4
     /   \
    2     6
     \
      3

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

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

Crédits

Les images ont été créées par habere-et-dispertire à l'aide de PGF/TikZ de Till Tantau.

Instructions spécifiques à CoffeeScript

Une instance de BinarySearchTree doit posséder 3 propriétés : data, left et right.

Une instance doit posséder ces méthodes :

• insert qui ajoute une nouvelle donnée à l'arbre. Cela ajoute un nouveau nœud « feuille » quelque part dans l'arbre.
• each qui prend un argument « callback ». C'est une fonction qui sera appelée sur chaque donnée de l'arbre dans l'ordre.

Cet exercice est un excellent terrain d'entraînement pour pratiquer la récursion.