Arbre de hauteur minimum

• La valeur médiane à la racine, puis récursivement les deux moitiés :

static AB abrhmin(int i, int j) {                 // abr de hauteur minimum sur [i:j]
    if (j - i <= 0) return null;                  // intervalle vide : arbre vide
    int k = (i + j) / 2;                          // valeur médiane
    return new AB(k, abrhmin(i, k), abrhmin(k + 1, j));
}

• On obtient un arbre de hauteur $3$ :

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

• Le niveau $l$ d'un arbre binaire contient au plus $2^l$ valeurs, donc un arbre de hauteur $h$ en contient au plus $1+2+\cdots +2^h=2^{h+1}-1$. Si $n\le 2^{h+1}-1$ alors $h\ge {\log }_2(n+1)-1$, et $h$ est entier. Pour $n=10$ : $h\ge \lceil {\log }_{2}11\rceil -1=3$ : abrhmin atteint bien le minimum.