Árbol de búsqueda binaria autoequilibrado

En informática , un árbol de búsqueda binaria autoequilibrado (BST) es cualquier árbol de búsqueda binaria basado en nodos que mantiene automáticamente su altura (número máximo de niveles por debajo de la raíz) pequeña ante inserciones y eliminaciones arbitrarias de elementos. ^{[ 1 ]} Estas operaciones, cuando se diseñan para un árbol de búsqueda binaria autoequilibrado, contienen medidas de precaución contra el aumento ilimitado de la altura del árbol, por lo que estas estructuras de datos abstractas reciben el atributo de "autoequilibrado".

Para árboles binarios equilibrados en altura , la altura se define como logarítmica.${\displaystyle O(\log n)}$en el número${\displaystyle n}$de elementos. Este es el caso de muchos árboles de búsqueda binaria, como los árboles AVL y los árboles rojo-negro . Los árboles Splay y los treaps se autoequilibran, pero no están equilibrados en altura, ya que no se garantiza que su altura sea logarítmica en el número de elementos.

Los árboles de búsqueda binaria autoequilibrados proporcionan implementaciones eficientes para listas ordenadas mutables y pueden utilizarse para otras estructuras de datos abstractas, como matrices asociativas , colas de prioridad y conjuntos .

La mayoría de las operaciones en un árbol de búsqueda binaria (BST) requieren 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⁰ ⁺ 2¹ + ^... + ^2h  =  2h + ^{1 -} 1 nodos. De ello se deduce que para cualquier árbol con n nodos y altura h :

${\displaystyle n\leq 2^{h+1}-1}$

Y eso implica:

${\displaystyle h\geq \lceil \log _{2}(n+1)-1\rceil \geq \lfloor \log _{2}n\rfloor }$.

En otras palabras, la altura mínima de un árbol binario con n nodos es log ₂ ( n ), redondeado hacia abajo ; es decir,${\displaystyle \lfloor \log _{2}n\rfloor }$. ^{[ 1 ]}

Sin embargo, los algoritmos más simples para la inserción de elementos en BST pueden generar un árbol de 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${\displaystyle \lfloor \log _{2}(1,000,000)\rfloor =19}$.

Si los datos se conocen de antemano, la altura promedio se puede mantener pequeña agregando valores en orden aleatorio, lo que da como resultado un árbol de búsqueda binaria aleatorio . Sin embargo, existen muchas situaciones (como en los algoritmos en línea ) donde esta aleatorización no es viable.

Los árboles binarios autoequilibrados resuelven este problema realizando transformaciones en el árbol (como rotaciones ) en los momentos de inserción clave, para mantener la altura proporcional a log₂ ( n ). Si bien _esto implica cierta sobrecarga , no es mayor que el costo de búsqueda siempre necesario y puede justificarse al garantizar una ejecución rápida de todas las operaciones.

Si bien es posible mantener un BST con altura mínima con esperada${\displaystyle O(\log n)}$En cuanto a las operaciones de tiempo (búsqueda/inserción/eliminación), los requisitos de espacio adicionales necesarios para mantener dicha estructura tienden a superar la disminución en el tiempo de búsqueda. A modo de comparación, un árbol AVL garantiza una altura dentro de un factor de 1,44 de la altura óptima, requiriendo 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${\displaystyle O(\log n)}$tiempo del peor caso y enumeración ordenada de todos los elementos en${\displaystyle O(n)}$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:

• Árbol AA
• Árbol AVL
• Árbol rojo-negro
• Árbol del chivo expiatorio
• Árbol de tango
• Trepa
• Árbol con peso equilibrado

Los árboles de búsqueda binaria 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 se insertan simplemente con un ordenamiento basado únicamente en la clave. En este sentido, 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 de clave , 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. 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 ] .}${\displaystyle O(\log n)}$en comparación con${\displaystyle O(n)}$), pero tienen un rendimiento promedio peor (${\displaystyle O(\log n)}$en comparación con${\displaystyle O(1)}$).

Los árboles binarios de búsqueda 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 ordenación de árboles binarios se implementa con un árbol binario de búsqueda autoequilibrado, tenemos un algoritmo muy sencillo de describir pero asintóticamente óptimo.${\displaystyle O(n\log n)}$algoritmo de ordenación. De manera similar, muchos algoritmos en geometría computacional aprovechan variaciones de los árboles binarios de búsqueda autoequilibrados para resolver problemas como el de intersección de segmentos de línea y el de localización de puntos de forma eficiente. (Sin embargo, en el caso promedio, los árboles binarios de búsqueda autoequilibrados pueden ser menos eficientes que otras soluciones. En particular, es probable que la ordenación por árbol binario sea más lenta que la ordenación por fusión , la ordenación rápida o la ordenación por montículos , debido a la sobrecarga del equilibrio del árbol y a los patrones de acceso a la caché ).

Los árboles binarios de búsqueda autoequilibrados son estructuras de datos flexibles, ya que es fácil extenderlos para registrar eficientemente información adicional 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.${\displaystyle O(\log n)}$tiempo. Estas extensiones se pueden utilizar, por ejemplo, para optimizar consultas de bases de datos u otros algoritmos de procesamiento de listas.

• Estructura de datos de búsqueda
• Algoritmo de Day-Stout-Warren
• Árbol de fusión
• Lista de saltos
• Clasificación

• Diccionario de algoritmos y estructuras de datos: Árbol de búsqueda binaria con altura equilibrada
• GNU libavl , una biblioteca con licencia LGPL de implementaciones de árboles binarios en C, con documentación