Árboles rojinegros
Una alternativa a los árboles AVL son los árboles rojinegros.
Aquí tenéis unas transparencias bastante autocontenidas:
Un applet para probarlos: aquí (seleccionar “R-B” en el panel de la derecha).
Y el capítulo de un libro con una implementación “top-down”: con código Java y con código C++ (acceso restringido, acceder con usuario y clave habituales).