En informática , un árbol binario de búsqueda autoequilibrado (BST) es cualquier árbol binario de búsqueda basado en nodos que mantiene automáticamente su altura (número máximo de niveles por debajo de la raíz) pequeña frente a inserciones y eliminaciones arbitrarias de elementos. [1] Estas operaciones, cuando están diseñadas para un árbol binario de búsqueda autoequilibrado, contienen medidas de precaución contra el aumento ilimitado de la altura del árbol, de modo que estas estructuras de datos abstractas reciben el atributo "autoequilibrado".
En el caso de los árboles binarios con equilibrio de altura , la altura se define como logarítmica en relación con el número de elementos. Este es el caso de muchos árboles binarios de búsqueda, como los árboles AVL y los árboles rojo-negro . Los árboles splay y los treaps se equilibran a sí mismos, pero no tienen equilibrio de altura, ya que no se garantiza que su altura sea logarítmica en relación con el número de elementos.
Los árboles de búsqueda binaria autoequilibrados proporcionan implementaciones eficientes para listas ordenadas mutables y pueden usarse para otras estructuras de datos abstractas como matrices asociativas , colas de prioridad y conjuntos .
La mayoría de las operaciones en un árbol binario de búsqueda (BST) toman un tiempo directamente proporcional a la altura del árbol, por lo que es conveniente 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 ; es decir, . [1]
Sin embargo, los algoritmos más simples para la inserción de elementos de BST pueden generar un árbol con una altura n en situaciones bastante comunes. Por ejemplo, cuando los elementos se insertan en orden de clave ordenado, el árbol degenera en una lista enlazada 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 un orden aleatorio, lo que da como resultado un árbol de búsqueda binario aleatorio . Sin embargo, hay muchas situaciones (como 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 de claves, para mantener la altura proporcional a log 2 ( n ). Aunque se involucra una cierta sobrecarga , no es mayor que el costo de búsqueda siempre necesario y puede justificarse al garantizar la ejecución rápida de todas las operaciones.
Si bien es posible mantener una BST con una altura mínima con las operaciones de tiempo esperadas (búsqueda/inserción/eliminación), los requisitos de espacio adicionales necesarios para mantener dicha estructura tienden a compensar la disminución del tiempo de búsqueda. A modo de comparación, se garantiza que un árbol AVL se encuentre dentro de un factor de 1,44 de la altura óptima mientras que 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 tiempo posible, 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 solo a través de comparaciones.
Las estructuras de datos que implementan este tipo de árbol incluyen:
Los árboles binarios de búsqueda autoequilibrados se pueden utilizar de forma natural para construir y mantener listas ordenadas, como las colas de prioridad . También se pueden utilizar para matrices asociativas ; los pares clave-valor se insertan simplemente con un ordenamiento 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 orden clave , 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. Los BST autoequilibrados 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 ).
Las BST autoequilibradas 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 se implementa la ordenación de árbol binario con una BST autoequilibrada, tenemos un algoritmo de ordenación asintóticamente óptimo pero muy simple de describir . De manera similar, muchos algoritmos en geometría computacional explotan variaciones en las BST autoequilibradas para resolver problemas como el problema de la intersección de segmentos de línea y el problema de ubicación de puntos de manera eficiente. (Sin embargo, para un rendimiento de caso promedio, las BST autoequilibradas pueden ser menos eficientes que otras soluciones. La ordenación de árbol binario, 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 por montículo , debido a la sobrecarga del equilibrio del árbol y a los patrones de acceso a la memoria caché ).
Las BST autoequilibradas son estructuras de datos flexibles, ya que es fácil extenderlas para registrar de manera eficiente información adicional o realizar nuevas operaciones. Por ejemplo, se puede registrar la cantidad de nodos en cada subárbol que tienen una determinada propiedad, lo que permite contar la cantidad de nodos en un determinado rango de claves con esa propiedad en el tiempo. Estas extensiones se pueden utilizar, por ejemplo, para optimizar las consultas de bases de datos u otros algoritmos de procesamiento de listas.
