Árbol de búsqueda binaria autoequilibrado - Self-balancing binary search tree

Un ejemplo de árbol desequilibrado ; seguir la ruta desde la raíz hasta un nodo requiere un promedio de 3,27 accesos a nodos

El mismo árbol después de haber sido equilibrado en altura; el esfuerzo de ruta promedio disminuyó a 3.00 accesos de nodo

En informática , un árbol de búsqueda binaria autoequilibrado es cualquier árbol de búsqueda binario 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. Estas operaciones, cuando se diseñan 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 abstractas reciben el atributo "autoequilibrado".

Para los árboles binarios de 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 ; este último se denominó árbol B binario simétrico y se renombró; Sin embargo, todavía se puede confundir con el concepto genérico de árbol de búsqueda binario autoequilibrado debido a las iniciales. ${\ Displaystyle {\ mathcal {O}} (\ log n)}$${\ Displaystyle n}$

Pero los árboles Splay y Treaps también se consideran autoequilibrados, aunque 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 se pueden utilizar para otras estructuras de datos abstractas, como matrices asociativas , colas de prioridad y conjuntos .

Visión general

Las rotaciones de árboles son operaciones internas muy comunes en árboles binarios autoequilibrados para mantener un equilibrio perfecto o casi perfecto.

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 ⁰ +2 ¹ + ··· + 2 ^h  = 2 ^{h +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}$

Sin embargo, los algoritmos más simples para la inserción de elementos BST pueden producir un árbol con altura n en situaciones bastante comunes. Por ejemplo, cuando los elementos se insertan en orden de clave ordenado, 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 . ${\ Displaystyle \ lfloor \ log _ {2} (1,000,000) \ rfloor = 19}$

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 los algoritmos en línea ) en las que esta aleatorización no es viable.

Los árboles binarios de autoequilibrio resuelven este problema realizando transformaciones en el árbol (como rotaciones de árboles ) en los momentos clave de inserción, para mantener la altura proporcional a log ₂ ( n ). Aunque se trata de una 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 las operaciones de tiempo esperado (búsqueda / inserción / eliminación), los requisitos de espacio adicional necesarios para mantener dicha estructura tienden a superar la disminución del tiempo de búsqueda. A modo de comparación, se garantiza que un árbol AVL está 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. Por lo tanto, la mayoría de los algoritmos BST de autoequilibrio mantienen la altura dentro de un factor constante de este límite inferior. ${\ Displaystyle O (\ log n)}$

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 O (log n ) en el peor de los casos, y la enumeración ordenada de todos los elementos en O ( n ) tiempo. Para algunas implementaciones, estos son límites de tiempo por operación, mientras que para otras son límites amortizados en una secuencia de operaciones. Estos tiempos son asintóticamente óptimos entre todas las estructuras de datos que manipulan la clave solo mediante comparaciones.

Implementaciones

Las estructuras de datos que implementan este tipo de árbol incluyen:

• 2-3 árboles
• Árbol AA
• Árbol AVL
• Árbol B
• Árbol rojo-negro
• Árbol de chivo expiatorio
• Árbol de extensión
• Árbol de tango
• Treap
• Árbol de peso equilibrado

Aplicaciones

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 simplemente se insertan con un orden basado solo en la clave. En esta capacidad, las BST autoequilibradas tienen una serie de ventajas y desventajas sobre su principal competidor, las tablas hash . Una ventaja de las BST de autoequilibrio 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. Las BST de autoequilibrio tienen un mejor rendimiento de búsqueda en el peor de los casos que las tablas hash (O (log n) en comparación con O (n)), pero tienen un peor rendimiento de casos promedio (O (log n) en comparación con O (1)).

Las BST de autoequilibrio 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 árbol binario se implementa con una BST autoequilibrada, tenemos un algoritmo de ordenación O ( n log n ) muy simple de describir pero asintóticamente óptimo . De manera similar, muchos algoritmos en geometría computacional aprovechan las variaciones en las BST autoequilibradas para resolver problemas como el problema de la intersección del segmento de línea y el problema de la ubicación del punto de manera eficiente. (Sin embargo, para el rendimiento de casos promedio, las BST de autoequilibrio 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 en pilas , debido a la sobrecarga de equilibrio del árbol como así como los patrones de acceso a la caché ).

Los BST de autoequilibrio son estructuras de datos flexibles, en el sentido de que es fácil extenderlos para registrar de manera eficiente 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 en el tiempo O (log n ). Estas extensiones se pueden utilizar, por ejemplo, para optimizar consultas de bases de datos u otros algoritmos de procesamiento de listas.

Ver también

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

Referencias

enlaces externos

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