Árboles ABB vs árboles AVL

Como sabemos, los árboles binarios de búsqueda son una estructura de datos que intenta conseguir mejor tiempo de acceso a los datos en las operaciones de búsqueda/recuperación, inserción o eliminación comparado con los tiempos en estructuras lineales como arreglos y listas. El acceso a un dato es proporcional a la altura del árbol, ya que su ubicación podría ser, en el peor de los casos, en una hoja. Por lo tanto, es deseable que el ABB tenga la menor altura posible;  pero esto dependerá de la secuencia en que los datos se fueron insertando en el momento de la creación del mismo. De esta forma, en el peor de los casos, la búsqueda puede llegar a tener orden de complejidad O(n).

Por otro lado, los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log2 n).