9. ABR (Arbre binaire de recherche)

Cf. TD4

Définition (ABR)

Soit un arbre binaire étiqueté par des valeurs qui peuvent être toujours comparées entre elles (i.e les valeurs sont donc des éléments d’un ensemble totalement ordonnés, par exemple les entiers).

On dit que c’est un arbre binaire de recherche si il vérifie :

• Soit c’est un arbre vide
• Soit :
  • Ses sous-arbre (gauche et droite) sont des ABR
  • Toutes les étiquettes du sous-arbre de gauche sont strictement inférieur à l’étiquette de la racine et toutes les étiquettes du sous-arbre de droite sont strictement supérieur à l’étiquette de la racine.

Exemple

8 3 16 17 23 2 5 3 1 9 7
En partant d’un arbre vide, on veut ajouter la liste de nombres.
On commence par 8, on l’ajoute (ass(anul(), anul(), 8)
Ensuite on ajoute 3, on l’ajoute en suivant la définition de l’ABR, donc on l’ajoute sur la gauche.
Ensuite pour le 16, en comparant 8 et 16 on se rend compe que 16 est plus grand que 8 donc on va a droite et on le met sur la case vide.
Pour 17, on va a droite car 8 < 17 et 16 < 17.
Etc, on procède récursivement jusqu’à atteindre cet arbre :

Remarque

Selon l’ordre d’ajout des éléments on peut obtenir des arbres différents, par exemple des arbres “file de fer”

Définition (profondeur d’un nœud)

Dans un arbre, la profondeur d’un noeud est le nombre de branche parcourues par un chemin entre la racine et ce nœud.

Définition (hauteur d’un arbre)

La hauteur d’un arbre est le maximum des profondeurs de ses nœuds.

Le nombre maximale de nœuds d’un arbre de hauteur h est : 2^{h+1}-1

Implantation en C

typedef struct noeudABR {
    int entier;
    struct noeudABR * g;
    struct noeudABR * d;
    void * objet; // utile pour les dictionnaires
    int hauteur; // utile pour équilibrer les arbres (voir chapitre 10)
} NoeudABR;
typedef NoeudABR * ABR;

void ajouter(ABR * arbre; int val) {
    if (*arbre == NULL) {
        *arbre = (NoeudABR*)malloc(sizeof(NoeudABR));
        if (*arbre == NULL) exit(1);
        (*arbre) -> entier = val;
        (*arbre) -> g = NULL;
        (*arbre) -> d = NULL;
    } else {
        if ((*arbre) -> entier < val) {
            ajouter(&(*arbre) -> d, val);
        }
        if ((*arbre) -> entier > val) {
            ajouter(&(*arbre) -> g, val);
        }
        /*
            Dans cet exemple, on ne fait rien si on a une égalité
            entre `(*arbre) -> entier` et `val`.
        */
    }
}

Pour retirer une racine, on doit mettre à la place de l’arbre qu’on retire quelque chose :

• Qui existe
• Qui respecte la cohérence de la définition d’un ABR

-> On récupère la valeur maximale de l’arbre et on met cette dernière à la place de la racine (dans ce cas là)

NoeudABR * ExtraireMax(ABR * a);
void       retirer(ABR * a, int val);