Problème — Un ABR équilibré à partir d'une liste triée

Problème — Un ABR équilibré à partir d'une liste triée.

On dispose d'une liste t de valeurs distinctes triée par ordre croissant. Insérer ses valeurs dans l'ordre produirait un arbre dégénéré.

• Écrire une fonction récursive abr_equilibre(t, g, d) qui renvoie un ABR contenant les valeurs t[g], …, t[d], en plaçant à la racine l'élément du milieu.
• Quelle est la hauteur de l'arbre obtenu pour $n=15$ ? pour $n=1000$ ? Combien de nœuds une recherche examine-t-elle au plus dans ce second cas ?
• Quel est le coût de la construction ?