Podríamos disminuir ese tiempo si mantuviéramos árboles de altura mínima (completos o casi-completos).

En ese caso el tiempo de búsqueda sería O(log N).
 

Idea:
Mantener el BST lo más equilibrado posible reequilibrándolo cada vez que insertemos, utilizando algoritmos de reequilibrado globales.

Ejemplo de algoritmos de reequilibrado de BST:

• Recorrido inorden seguido de reconstrucción a partir del véctor ordenado
• El algoritmo DSW (C. Day, Q. Stout y B. Warren).

El coste de los algoritmos de reequilibrado puede ser O(N)

Así que tenemos:

• búsqueda en árbol equilibrado: O(log N), pero
• inserción y reequilibrado: O(N).

Pregunta:

¿Hay forma de alcanzar búsqueda en tiempo O(log N) y a la vez inserción en tiempo O(log N)?

Respuesta:

SI 
 

• La idea es definir una clase de BST que sean casi equilibrados y usar una técnica de reequilibrado local.
• En este caso se puede demostrar que podemos tener tiempos de inserción y búsqueda O(log N).

Un método clásico para hacer esto es usar un árbol  AVL (Adelson-Velskii y Landis).