TDD - Arbres binaires de recherche

Frédéric Chyzak
[Solution]
On considère le modèle des arbres binaires de recherche (en anglais binary search tree), c'est-à-dire d'arbres binaires étiquetés de façon que toutes les étiquettes des sommets du sous-arbre gauche d'un sommet s soient plus petites que celle du sommet s et que toutes celles du sous-arbre droit soient plus grandes. (Ici, on veut dire plus petites et plus grandes strictement ; il n'y a donc pas de répétition possible des étiquettes.) Ces familles d'arbres sont une structure de données adaptée pour classer des objets ; dans une certain nombre d'applications, il est plus avantageux d'utiliser des arbres binaires de recherche plutôt que des tableaux triés. Le but de ce sujet est d'étudier divers mode d'insertion ainsi que leurs propriétés sur l'équilibrage des arbres.

Insertion aux feuilles

On se donne le type 
    typedef struct cell { int va; struct cell *ga,*dr; } *BST;

Écrire les fonctions 

    BST new_BST(int n,BST g,BST d);
    BST insert(int n,BST b);
    int height(BST b);
    int size(BST b);
    void prefix(BST b);
à savoir respectivement : un constructeur d'arbre binaire de recherche, une fonction d'insertion aux feuilles de la valeur n, une fonction de calcul de la hauteur de l'arbre, une fonction de calcul de sa taille, et une fonction d'affichage des valeurs de l'arbre le long d'un parcourt préfixe gauche. La fonction d'insertion parcourera récursivement l'arbre b en cheminant de la racine vers les feuilles et renverra l'arbre modifié.

On se convainc aisément que si l'on insère successivement des entiers 1, 2, ..., N à partir de l'arbre vide, l'arbre obtenu est très déséquilibré et de hauteur N. La recherche dans un tel arbre coûte donc en moyenne O(N) unités de temps. Le vérifier expérimentalement.

Insertion à la racine

Un autre mode d'insertion possible est à la racine : l'idée est alors de se servir de la valeur n à insérer comme pivot afin de séparer l'arbre b en un arbre binaire de recherche b< contenant les valeurs plus petites que n et en un autre b> contenant celles plus grandes. L'insertion à la racine est immédiate une fois la séparation réalisée : il suffit alors de créer un sommet dont les deux fils sont b< et b>. Pour décrire la séparation, notons b=(g,v,d) un arbre dont la racine contient la valeur v et dont les fils gauche et droit sont respectivement g et d. Lorsque le pivot n est plus petit que v, la séparation de b renvoie la paire donnée par b<=g< et b>=(g>,v,d) ; lorsqu'il est plus grand, elle renvoie la paire donnée par b<=(g,v,d<) et b>=d>.

On a ainsi besoin d'un nouveau type pour représenter les paires d'arbres, 

    typedef struct pair { BST ga; BST dr; } *Pair;
et on demande d'écrire les fonctions 
    Pair split(int n,BST b);
    BST root_insert(int n,BST b);
de séparation (qui sera récursive) et d'insertion à la racine.

Ici encore, vérifier expérimentalement que si l'on insère successivement des entiers 1, 2, ..., N à partir de l'arbre vide, l'arbre obtenu est très déséquilibré et de hauteur N, d'où une recherche en temps moyen O(N).

Adjonction des tailles des arbres

Lorsqu'on insère N valeurs dans un arbre binaire de recherche, la hauteur minimale que l'on est en droit d'espérer est (à un près) ln2N. On va petit à petit mettre en oeuvre une méthode qui permette de garantir, en moyenne, que l'insertion successive des entiers 1, 2, ..., N à partir de l'arbre vide construise un arbre de hauteur O(ln2N), d'où une recherche en temps moyen ramenée elle aussi à O(ln2N). Cette randomisation s'appuiera sur la taille des arbres, et on commence donc par étendre les structures d'arbres des questions précédentes pour contenir la taille des sous-arbres.

Plus précisément, on ajoute à chaque sommet l'information de la taille d'un des deux sous-arbres, ainsi que de celui sous-arbres dont on a la taille. Toutes les opérations récursives mettent à jour ces informations. On obtient ainsi les nouveaux types 

    typedef enum orientation { GAUCHE, DROITE } Orientation;
    typedef struct scell {
      int va,ta;
      Orientation or;
      struct scell *ga,*dr; } *sBST;
    typedef struct spair { int ta; Orientation or; sBST ga; sBST dr; } *sPair;
La raison pour ne conserver la taille d'un seul des deux sous-arbres est d'éviter, après une insertion à une feuille, d'avoir à rétropropager l'incrémentation de la taille. Il faut donc aussi se doter d'une variable globale taille pour sauvegarder la taille de l'arbre dans lequel on opère récursivement.

Recopier et modifier les fonctions des questions précédentes de façon à écrire des fonctions 

    sBST new_sBST(int n,int t,Orientation o,sBST g,sBST d);
    sBST sinsert(int n,sBST b,int t);
    int sheight(sBST b);
    void sprefix(sBST b,int t);
    sPair new_sPair(int t,Orientation o,sBST g,sBST d);
    sPair ssplit(int n,sBST b,int t);
    sBST root_sinsert(int n,sBST b,int t);
opérant sur les nouvelles structures de données. Dans les cas où une orientation o fait partie des entrées, t est la taille du sous-arbre ou de l'élément de la paire indiqué par cette orientation. Dans les autres cas, t est la taille de l'arbre b.

Randomisation et arbres binaires de recherche équilibrés

On s'intéresse enfin à l'algorithme randomisé suivant : lorsqu'une valeur est à insérer dans un arbre de taille t, on choisit de l'insérer par l'algorithme d'insertion à la racine avec probabilité 1/(t+1), où de l'insérer récursivement dans le sous-arbre adéquat avec probabilité t/(t+1), cette insertion récursive étant elle-même randomisée. On peut montrer qu'alors la hauteur des arbres binaires de recherche obtenus est en moyenne logarithmique, même en présence de longues séquences d'insertion d'entiers successifs.

Implanter la fonction randomisée 

    sBST randomized_sinsert(int n,sBST b,int t);
et vérifier expérimentalement que l'insertion successive des entiers 1, 2, ..., N à partir de l'arbre vide fournit un arbre déséquilibré de hauteur O(ln2N), d'où une recherche en temps moyen O(ln2N).

Pour aller plus loin

Des algorithmes pour la suppression d'un élément d'un arbre binaire de recherche et ayant des propriétés similaires sont disponibles et sont décrits ici.
Frédéric Chyzak
Last modified: Mon Jun 10 16:48:36 CEST 2002