En informática , un árbol de búsqueda binario autoequilibrado (o equilibrado en altura ) 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 de elementos arbitrarios. [1]
Estas estructuras 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 .
El árbol rojo-negro , que es un tipo de árbol de búsqueda binario autoequilibrado, se denominó árbol B binario simétrico [2] y se le cambió el nombre, pero aún puede confundirse con el concepto genérico de árbol de búsqueda binario autoequilibrado debido a la iniciales.
Descripción general
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 ; es decir,. [1]
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.
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 2 ( n ). Aunque se trata de una cierta sobrecarga , a la larga se puede justificar si se garantiza una ejecución rápida de las operaciones posteriores.
Si bien es posible mantener un BST con una altura mínima con la esperada operaciones de tiempo (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 estará 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 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:
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 autoequilibradas es que permiten una enumeración rápida (de hecho, asintóticamente óptima) de los elementos en orden de 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 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 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
- ^ a b c Donald Knuth . El arte de la programación informática , volumen 3: clasificación y búsqueda , segunda edición. Addison-Wesley, 1998. ISBN 0-201-89685-0 . Sección 6.2.3: Árboles equilibrados, págs. 458–481.
- ^ Paul E. Black , "árbol rojo-negro", en Dictionary of Algorithms and Data Structures [en línea], Vreda Pieterse y Paul E. Black, eds. 13 de abril de 2015. (consultado el 3 de octubre de 2016) Disponible en: https://xlinux.nist.gov/dads/HTML/redblack.html
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