Arbre binaire de recherche

Instructions

Insérer et rechercher 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 qu'on ait le tableau [1, 3, 4, 5] et qu'on y ajoute 2, ce qui donne [1, 3, 4, 5, 2]. Il faut maintenant trier tout le tableau à nouveau ! On peut faire mieux 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, 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 connectés. 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

Crédits

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