En informática , un árbol de búsqueda binario (BST) autoequilibrado es cualquier árbol de búsqueda binario basado en nodos que automáticamente mantiene pequeña su altura (número máximo de niveles debajo de la raíz) frente a inserciones y eliminaciones arbitrarias de elementos. [1] Estas operaciones, cuando están diseñadas para un árbol de búsqueda binario autoequilibrado, contienen medidas de precaución contra el aumento ilimitado de la altura del árbol, de modo que estas estructuras de datos abstractos reciben el atributo "autoequilibrio".
Para árboles binarios con altura equilibrada , la altura se define como logarítmica en el número de elementos. Este es el caso de muchos árboles de búsqueda binarios, como los árboles AVL y los árboles rojo-negro . Los árboles extendidos y los treaps se equilibran por sí solos, pero no en altura, ya que no se garantiza que su altura sea logarítmica en el número de elementos.
Los árboles de búsqueda binarios autoequilibrados proporcionan implementaciones eficientes para listas ordenadas mutables y pueden usarse para otras estructuras de datos abstractos, como matrices asociativas , colas y conjuntos de prioridad .
La mayoría de las operaciones en un árbol de búsqueda binaria (BST) toman un tiempo directamente proporcional a la altura del árbol, por lo que es deseable mantener la altura pequeña. Un árbol binario con altura h puede contener como máximo 2 0 +2 1 +···+2 h = 2 h +1 −1 nodos. De ello se deduce que para cualquier árbol con n nodos y altura h :
Y eso implica:
En otras palabras, la altura mínima de un árbol binario con n nodos es log 2 ( n ), redondeado hacia abajo ; eso es, . [1]
Sin embargo, los algoritmos más simples para la inserción de elementos BST pueden generar un árbol con altura n en situaciones bastante comunes. Por ejemplo, cuando los elementos se insertan en orden de clave , el árbol degenera en una lista vinculada con n nodos. La diferencia de rendimiento entre las dos situaciones puede ser enorme: por ejemplo, cuando n = 1.000.000, la altura mínima es .
Si los elementos de datos se conocen de antemano, la altura se puede mantener pequeña, en el sentido promedio, agregando valores en orden aleatorio, lo que da como resultado un árbol de búsqueda binario aleatorio . Sin embargo, hay muchas situaciones (como los algoritmos en línea ) en las que esta aleatorización no es viable.
Los árboles binarios autoequilibrados resuelven este problema realizando transformaciones en el árbol (como rotaciones de árbol ) en momentos de inserción clave, para mantener la altura proporcional a log 2 ( n ). Aunque implica cierta sobrecarga , no es mayor que el costo de búsqueda siempre necesario y puede justificarse asegurando una ejecución rápida de todas las operaciones.
Si bien es posible mantener un BST con una altura mínima con operaciones en el tiempo esperado (búsqueda/inserción/eliminación), los requisitos de espacio adicionales necesarios para mantener dicha estructura tienden a compensar la disminución en el tiempo de búsqueda. A modo de comparación, se garantiza que un árbol AVL estará dentro de un factor de 1,44 de la altura óptima y requiere solo dos bits adicionales de almacenamiento en una implementación ingenua. [1] Por lo tanto, la mayoría de los algoritmos BST autoequilibrados mantienen la altura dentro de un factor constante de este límite inferior.
En el sentido asintótico (" Big-O "), una estructura BST autoequilibrada que contiene n elementos permite la búsqueda, inserción y eliminación de un elemento en el peor de los casos, y la enumeración ordenada de todos los elementos en el tiempo. Para algunas implementaciones, estos son límites de tiempo por operación, mientras que para otras son límites amortizados a lo largo de una secuencia de operaciones. Estos tiempos son asintóticamente óptimos entre todas las estructuras de datos que manipulan la clave únicamente mediante comparaciones.
Las estructuras de datos que implementan este tipo de árbol incluyen:
Los árboles de búsqueda binarios autoequilibrados se pueden utilizar de forma natural para construir y mantener listas ordenadas, como colas de prioridad . También se pueden utilizar para matrices asociativas ; Los pares clave-valor simplemente se insertan con un orden basado únicamente en la clave. En esta capacidad, los BST autoequilibrados tienen una serie de ventajas y desventajas sobre su principal competidor, las tablas hash . Una ventaja de los BST autoequilibrados es que permiten una enumeración rápida (de hecho, asintóticamente óptima) de los elementos en el orden de las claves , algo que las tablas hash no proporcionan. Una desventaja es que sus algoritmos de búsqueda se vuelven más complicados cuando puede haber varios elementos con la misma clave. Las BST autoequilibradas tienen un mejor rendimiento de búsqueda en el peor de los casos que la mayoría de las tablas hash [2] ( en comparación con ), pero tienen un peor rendimiento en el caso promedio ( en comparación con ).
Los BST autoequilibrados se pueden utilizar para implementar cualquier algoritmo que requiera listas ordenadas mutables, para lograr un rendimiento asintótico óptimo en el peor de los casos. Por ejemplo, si la clasificación de árbol binario se implementa con un BST autoequilibrado, tenemos un algoritmo de clasificación muy simple de describir pero asintóticamente óptimo . De manera similar, muchos algoritmos en geometría computacional explotan variaciones en BST autoequilibrados para resolver problemas como el problema de intersección de segmentos de línea y el problema de ubicación de puntos de manera eficiente. (Sin embargo, para un rendimiento promedio, los BST con autoequilibrio pueden ser menos eficientes que otras soluciones. La ordenación de árboles binarios, en particular, es probable que sea más lenta que la ordenación por combinación , la ordenación rápida o la ordenación en montón, debido a la sobrecarga del equilibrio de árboles como así como patrones de acceso a la caché ).
Los BST autoequilibrados son estructuras de datos flexibles, ya que es fácil extenderlos para registrar información adicional de manera eficiente o realizar nuevas operaciones. Por ejemplo, se puede registrar el número de nodos en cada subárbol que tiene una determinada propiedad, lo que permite contar el número de nodos en un determinado rango de claves con esa propiedad en el tiempo. Estas extensiones se pueden utilizar, por ejemplo, para optimizar consultas de bases de datos u otros algoritmos de procesamiento de listas.
