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.

Implémentation

Implémenter une structure d'arbre efficace et modifiable en Cairo (ou dans n'importe quel langage purement fonctionnel à mémoire immuable) est un vrai défi, car ces langages sont conçus pour éviter de modifier les données une fois qu'elles sont créées. Cette immuabilité implique que, plutôt que de mettre à jour un nœud de l'arbre directement, il faut créer une nouvelle version de l'arbre à chaque modification.

Pour montrer pourquoi, imagine une structure d'arbre binaire simple où chaque nœud possède un enfant gauche et un enfant droit. Prenons un petit arbre comme celui-ci :

       1
      / \
     2   3

Maintenant, supposons que l'on veuille ajouter un nouveau nœud 4 comme enfant gauche du nœud 2. Dans un langage purement fonctionnel (comme Cairo ou Haskell), la mémoire est immuable, on ne peut donc pas simplement ajouter le nœud 4 directement à 2. À la place, il faut créer une nouvelle version de chaque nœud le long du chemin qui va de la racine au nœud modifié, car chacun de ces nœuds pointe désormais vers un sous-arbre nouveau ou modifié.

Voici à quoi ressemblerait le processus :

1. Ajoute le nœud 4 au nœud 2 :

   • Crée une nouvelle version du nœud 2, qui a désormais 4 comme enfant gauche.

       2'
      / 
     4   
   

2. Mets à jour le nœud racine :

   • Comme le nœud 1 pointait à l'origine vers l'ancien 2, on crée une nouvelle version du nœud racine 1' qui pointe désormais vers le nœud 2' mis à jour à gauche et conserve le nœud 3 à droite.

       1'
      / \
     2'  3
   

L'arbre obtenu devient donc :

       1'
      / \
     2'  3
    /
   4

Ce nouvel arbre (1') ressemble toujours à l'original, mais avec un chemin mis à jour. Le point essentiel est qu'il a fallu recréer chaque nœud le long du chemin (1 vers 2) pour préserver l'immuabilité, puisque les nœuds existants ne peuvent pas être modifiés sur place. L'arbre d'origine existe toujours (par exemple, pour toutes les références à sa racine d'origine 1), tandis que ce nouvel arbre représente l'état modifié.

Dans les grands arbres, cette approche peut devenir coûteuse, car chaque nouvelle modification oblige à recréer un chemin de nœuds allant de la racine au nœud mis à jour, même si seule une petite partie de l'arbre change réellement.