De très nombreuses références existent sur le Net, qu'on trouve sans problème via Google. J'ai vu programmer ce type d'algoritme en C ou C++, mais sans plonger moi-même dans le source.
J'en ai quand même retenu quelques leçons. Pour construire l'arbre, on a besoin d'une fonction de recherche (identique à celle qui servira à l'utilisation des données) pour traiter le cas des doubles qui se doit d'être performante. La difficulté est donc d'avoir un arbre en permanence équilibré, ce qui conduit à modifier la racine de l'arbre général et/ou des sous-arbres qui le composent, de manière à limiter la profondeur de la recherche. Il faut donc prévoir une primitive qui permette cette opération. Si mes souvenirs sont bons, cette opération nécessite de gérer un compteur d'objets au niveau de chaque noeud.
Algorithmique arbre binaire iteratif