Insérer et rechercher

• L'insertion descend à gauche ou à droite comme une recherche, et reconstruit le chemin parcouru :

static AB inserer(int x, AB a) {
    if (vide(a)) return new AB(x, null, null);        // x devient une feuille
    if (x == vr(a)) return a;                         // x est déjà dans a
    if (x < vr(a)) return new AB(vr(a), inserer(x, sag(a)), sad(a));
    return new AB(vr(a), sag(a), inserer(x, sad(a)));
}

• La dichotomie : chaque comparaison élimine un des deux sous-arbres.

static AB dans(int v, AB a) {
    if (vide(a) || v == vr(a)) return a;              // absent, ou trouvé
    if (v < vr(a)) return dans(v, sag(a));            // v ne peut être qu'à gauche
    return dans(v, sad(a));                           // v ne peut être qu'à droite
}

• On obtient l'arbre ci-dessous, de hauteur $3$ :

(5 (3 (1 () (2 () ())) (4 () ())) (8 (7 (6 () ()) ()) (9 () ())))

Pour trouver $6$, on le compare à $5$, $8$, $7$ puis $6$ : quatre comparaisons, son niveau plus un. Pour $10$ : $5$, $8$, $9$, puis l'arbre vide à droite de $9$ : trois comparaisons.

• Les insertions $1,2,3,4,5$ donnent un arbre dégénéré : chaque valeur est insérée à droite de la précédente, $(1()(2()(3()(4()(5()())))))$, de hauteur $4$. C'est une liste : une recherche y coûte jusqu'à $n$ comparaisons, et les $n$ insertions coûtent en tout $1+2+\cdots +(n-1)$, soit $\Theta (n^2)$.