Árbol de búsqueda binaria

En informática , un árbol de búsqueda binaria ( BST ), también llamado árbol binario ordenado , es una estructura de datos de árbol binario con raíz , donde la clave de cada nodo interno es mayor que todas las claves de su subárbol izquierdo y menor que las de su subárbol derecho. La complejidad temporal de las operaciones en el árbol de búsqueda binaria es lineal con respecto a la altura del árbol.

Los árboles de búsqueda binaria permiten realizar búsquedas binarias para la rápida consulta, adición y eliminación de elementos de datos. Dado que los nodos de un árbol de búsqueda binaria están dispuestos de manera que cada comparación omite aproximadamente la mitad del árbol restante, el rendimiento de la búsqueda es proporcional al del logaritmo binario . Los árboles de búsqueda binaria se idearon en la década de 1960 para el problema del almacenamiento eficiente de datos etiquetados y se atribuyen a Conway Berners-Lee y David Wheeler .

El rendimiento de un árbol de búsqueda binaria depende del orden de inserción de los nodos, ya que las inserciones arbitrarias pueden provocar degeneración. Se pueden construir varias variantes del árbol de búsqueda binaria con un rendimiento garantizado en el peor de los casos. Las operaciones básicas incluyen: búsqueda, recorrido, inserción y eliminación. Los árboles de búsqueda binaria con complejidad garantizada en el peor de los casos tienen un mejor rendimiento que un arreglo sin ordenar, que requeriría un tiempo de búsqueda lineal .

El análisis de complejidad de BST muestra que, en promedio , las operaciones de inserción, eliminación y búsqueda toman $\Theta (\log n)$ para $n$ nodos. En el peor de los casos, se degradan hasta convertirse en una lista enlazada simple: $O(n)$ Para abordar el aumento ilimitado de la altura del árbol con inserciones y eliminaciones arbitrarias, se introducen variantes autoequilibradas de los árboles de búsqueda binaria (BST) para limitar la complejidad de búsqueda en el peor de los casos a la del logaritmo binario. Los árboles AVL fueron los primeros árboles de búsqueda binaria autoequilibrados, inventados en 1962 por Georgy Adelson-Velsky y Evgenii Landis . ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]}

Los árboles de búsqueda binaria se pueden utilizar para implementar tipos de datos abstractos como conjuntos dinámicos , tablas de búsqueda y colas de prioridad , y también en algoritmos de ordenación como la ordenación en árbol .

Historia

El algoritmo de árbol de búsqueda binaria fue descubierto independientemente por varios investigadores, entre ellos PF Windley, Andrew Donald Booth , Andrew Colin y Thomas N. Hibbard . ^{[ 4 ]}^{[ 5 ]} El algoritmo se atribuye a Conway Berners-Lee y David Wheeler , quienes lo utilizaron para almacenar datos etiquetados en cintas magnéticas en 1960. ^{[ 6 ]} Uno de los primeros y más populares algoritmos de árbol de búsqueda binaria es el de Hibbard. ^{[ 4 ]}

La complejidad temporal de un árbol de búsqueda binaria aumenta indefinidamente con la altura del árbol si los nodos se insertan en un orden arbitrario; por lo tanto, se introdujeron árboles de búsqueda binaria autoequilibrados para limitar la altura del árbol a $O(\log n)$ . ^{[ 7 ]} Se introdujeron varios árboles de búsqueda binaria con altura equilibrada para limitar la altura del árbol, como los árboles AVL , Treaps y árboles rojo-negro . ^{[ 8 ]}

Descripción general

Un árbol de búsqueda binaria es un árbol binario con raíz en el que los nodos se organizan en estricto orden total, de modo que los nodos con claves mayores que cualquier nodo A se almacenan en los subárboles derechos de dicho nodo A, y los nodos con claves iguales o menores que A se almacenan en los subárboles izquierdos de A, cumpliendo así la propiedad de búsqueda binaria . ^{[ 9 ]}^{: 298}^{[ 10 ]}^{: 287}

Los árboles de búsqueda binaria también son eficaces en algoritmos de ordenación y búsqueda . Sin embargo, la complejidad de búsqueda de un árbol de búsqueda binaria depende del orden en que se insertan y eliminan los nodos; dado que, en el peor de los casos, las operaciones sucesivas en el árbol de búsqueda binaria pueden conducir a la degeneración y formar una estructura similar a una lista enlazada simple (o "árbol desequilibrado"), tiene, por lo tanto, la misma complejidad en el peor de los casos que una lista enlazada . ^[¹¹^]^[⁹^]^:^299-302

Los árboles de búsqueda binaria son también una estructura de datos fundamental utilizada en la construcción de estructuras de datos abstractas como conjuntos, multiconjuntos y matrices asociativas .

Operaciones

Búsqueda

La búsqueda de una clave específica en un árbol de búsqueda binaria se puede programar de forma recursiva o iterativa .

La búsqueda comienza examinando el nodo raíz . Si el árbol es $nulo$ , la clave que se busca no existe en el árbol. De lo contrario, si la clave es igual a la de la raíz, la búsqueda es exitosa y se devuelve el nodo. Si la clave es menor que la de la raíz, la búsqueda continúa examinando el subárbol izquierdo. De manera similar, si la clave es mayor que la de la raíz, la búsqueda continúa examinando el subárbol derecho. Este proceso se repite hasta que se encuentra la clave o se encuentra el subárbol restante. ${\text{nil}}$ . Si la clave buscada no se encuentra después de un ${\text{nil}}$ Se alcanza el subárbol, por lo que la clave no está presente en el árbol. ^{[ 10 ]}^{: 290–291}

Búsqueda recursiva

El siguiente pseudocódigo implementa el procedimiento de búsqueda BST mediante recursión . ^{[ 10 ]}^{: 290}

El procedimiento recursivo continúa hasta que se ${\text{nil}}$ o el ${\text{clave}}$ Se encuentran siendo buscados.

Búsqueda iterativa

La versión recursiva de la búsqueda se puede "desenrollar" en un bucle while . En la mayoría de las máquinas, se ha comprobado que la versión iterativa es más eficiente . ^{[ 10 ]}^{: 291}

Dado que la búsqueda puede continuar hasta algún nodo hoja , la complejidad temporal de la búsqueda BST es $O(h)$ dónde $h$ es la altura del árbol . Sin embargo, el peor caso para la búsqueda BST es $O(n)$ dónde $n$ es el número total de nodos en el BST, porque un BST desequilibrado puede degenerar en una lista enlazada. Sin embargo, si el BST está equilibrado en altura, la altura es $O(\log n)$ . ^{[ 10 ]}^{: 290}

Sucesor y predecesor

Para ciertas operaciones, dado un nodo ${\text{x}}$ encontrar al sucesor o predecesor de ${\text{x}}$ es crucial. Suponiendo que todas las claves de un BST son distintas, el sucesor de un nodo ${\text{x}}$ en un BST es el nodo con la clave más pequeña mayor que ${\text{x}}$ clave de. Por otro lado, el predecesor de un nodo ${\text{x}}$ en un BST es el nodo con la clave más grande menor que ${\text{x}}$ clave de. El siguiente pseudocódigo encuentra el sucesor y el predecesor de un nodo. ${\text{x}}$ en un BST. ^{[ 12 ]}^{[ 13 ]}^{[ 10 ]}^{: 292–293}

Las operaciones como encontrar un nodo en un árbol binario de búsqueda (BST) cuya clave sea la máxima o la mínima son cruciales en ciertas operaciones, como determinar el sucesor y el predecesor de los nodos. A continuación se presenta el pseudocódigo para dichas operaciones. ^{[ 10 ]}^{: 291–292}

Inserción

Operaciones como la inserción y la eliminación provocan que la representación del BST cambie dinámicamente. La estructura de datos debe modificarse de tal manera que las propiedades del BST se mantengan. Los nuevos nodos se insertan como nodos hoja en el BST. ^{[ 10 ]}^{: 294–295} A continuación se presenta una implementación iterativa de la operación de inserción. ^{[ 10 ]}^{: 294}

El procedimiento mantiene un "puntero de seguimiento". ${\text{y}}$ como padre de ${\text{x}}$ . Después de la inicialización en la línea 2, el bucle while en las líneas 4-11 hace que los punteros se actualicen. Si ${\text{y}}$ es ${\text{nil}}$ , el BST está vacío, por lo tanto ${\text{z}}$ se inserta como nodo raíz del árbol de búsqueda binaria ${\text{T}}$ , si no lo es ${\text{nil}}$ , la inserción procede comparando las claves con las de ${\text{y}}$ en las líneas 15-19 y el nodo se inserta en consecuencia. ^{[ 10 ]}^{: 295}

Supresión

La eliminación de un nodo, por ejemplo ${\text{Z}}$ , del árbol de búsqueda binaria ${\text{BST}}$ tiene tres casos: ^{[ 10 ]}^{: 295-297}

Si ${\text{Z}}$ es un nodo hoja, es reemplazado por ${\text{NINGUNO}}$ como se muestra en (a).
Si ${\text{Z}}$ tiene solo un hijo, el nodo hijo de ${\text{Z}}$ se eleva modificando el nodo padre de ${\text{Z}}$ para apuntar al nodo hijo, tomando en consecuencia ${\text{Z}}$ su posición en el árbol, como se muestra en (b) y (c).
Si ${\text{Z}}$ ${\text{Z}}$ tiene hijos tanto a la izquierda como a la derecha, el sucesor en orden de ${\text{Z}}$ ${\text{Z}}$ , decir ${\text{Y}}$ ${\text{Y}}$ , desplaza ${\text{Z}}$ ${\text{Z}}$ siguiendo los dos casos:
1. Si ${\text{Y}}$ es ${\text{Z}}$ hijo derecho, como se muestra en (d), ${\text{Y}}$ desplaza ${\text{Z}}$ y ${\text{Y}}$ El hijo derecho permanece sin cambios.
2. Si ${\text{Y}}$ se encuentra dentro ${\text{Z}}$ subárbol derecho pero no lo es ${\text{Z}}$ hijo derecho, como se muestra en (e), ${\text{Y}}$ primero es reemplazado por su propio hijo legítimo, y luego lo desplaza. ${\text{Z}}$ su posición en el árbol.
Como alternativa, también se puede utilizar el predecesor en orden.

El siguiente pseudocódigo implementa la operación de eliminación en un árbol de búsqueda binaria. ^{[ 10 ]}^{: 296-298}

El ${\text{BST-Eliminar}}$ El procedimiento se ocupa de los 3 casos especiales mencionados anteriormente. Las líneas 2-3 se ocupan del caso 1; las líneas 4-5 se ocupan del caso 2 y las líneas 6-16 del caso 3. La función auxiliar ${\text{Nodos de cambio}}$ se utiliza dentro del algoritmo de eliminación con el propósito de reemplazar el nodo ${\text{u}}$ con ${\text{v}}$ en el árbol de búsqueda binaria ${\text{BST}}$ . ^{[ 10 ]}^{: 298} Este procedimiento maneja la eliminación (y sustitución) de ${\text{u}}$ de ${\text{BST}}$ .

Recorrido

Un árbol de búsqueda binaria (BST) se puede recorrer mediante tres algoritmos básicos: recorridos en orden , en preorden y en postorden . ^{[ 10 ]}^{: 287}

Recorrido en orden : Primero se visitan los nodos del subárbol izquierdo, seguidos del nodo raíz y el subárbol derecho. Este recorrido visita todos los nodos en el orden de la secuencia de claves no decreciente.
Recorrido de árbol en preorden : Primero se visita el nodo raíz, seguido de los subárboles izquierdo y derecho.
Recorrido de árbol en postorden : Primero se visitan los nodos del subárbol izquierdo, seguidos del subárbol derecho y, finalmente, la raíz.

A continuación se presenta una implementación recursiva de los recorridos de árboles. ^{[ 10 ]}^{: 287–289}

Árboles de búsqueda binaria equilibrados

Sin reequilibrio, las inserciones o eliminaciones en un árbol de búsqueda binaria pueden conducir a la degeneración, lo que resulta en una altura $n$ del árbol (donde $n$ es el número de elementos en un árbol), de modo que el rendimiento de la búsqueda se deteriora al de una búsqueda lineal. ^{[ 14 ]} Mantener el árbol de búsqueda equilibrado y con la altura limitada por $O(\log n)$ es clave para la utilidad del árbol de búsqueda binaria. Esto se puede lograr mediante mecanismos de "autoequilibrio" durante las operaciones de actualización del árbol, diseñados para mantener la altura del árbol en la complejidad logarítmica binaria. ^{[ 7 ]}^{[ 15 ]}^{: 50}

Árboles de altura equilibrada

Un árbol está equilibrado en altura si se garantiza que las alturas del subárbol izquierdo y del subárbol derecho están relacionadas por un factor constante. Esta propiedad fue introducida por el árbol AVL y continuada por el árbol rojo-negro . ^{[ 15 ]}^{: 50–51} Las alturas de todos los nodos en la ruta desde la raíz hasta el nodo hoja modificado deben observarse y posiblemente corregirse en cada operación de inserción y eliminación en el árbol. ^{[ 15 ]}^{: 52}

Árboles con peso equilibrado

En un árbol equilibrado por peso, el criterio de un árbol equilibrado es el número de hojas de los subárboles. Los pesos de los subárboles izquierdo y derecho difieren como máximo en $1$ . ^{[ 16 ]}^{[ 15 ]}^{: 61} Sin embargo, la diferencia está limitada por una razón $\alpha$ de los pesos, ya que una fuerte condición de equilibrio de $1$ no se puede mantener con $O(\log n)$ reequilibrio del trabajo durante las operaciones de inserción y eliminación. $\alpha$ Los árboles equilibrados por peso proporcionan una familia completa de condiciones de equilibrio, donde cada subárbol izquierdo y derecho tiene al menos una fracción de $\alpha$ del peso total del subárbol. ^{[ 15 ]}^{: 62}

Tipos

Hay varios árboles de búsqueda binaria autoequilibrados, incluyendo el árbol T , ^{[ 17 ]} treap , ^{[ 18 ]} árbol rojo-negro , ^{[ 19 ]} árbol B , ^{[ 20 ]} árbol 2–3 , ^{[ 21 ]} y árbol Splay . ^{[ 22 ]}

Ejemplos de aplicaciones

Clasificar

Los árboles de búsqueda binaria se utilizan en algoritmos de ordenación como el ordenamiento por árbol , donde todos los elementos se insertan a la vez y el árbol se recorre en orden. ^{[ 23 ]} Los BST también se utilizan en el ordenamiento rápido . ^{[ 24 ]}

Operaciones de cola de prioridad

Los árboles de búsqueda binaria se utilizan en la implementación de colas de prioridad , usando la clave del nodo como prioridad. Agregar nuevos elementos a la cola sigue la operación de inserción regular de BST, pero la operación de eliminación depende del tipo de cola de prioridad: ^{[ 25 ]}

Si se trata de una cola de prioridad ascendente, la eliminación del elemento con la prioridad más baja se realiza mediante un recorrido hacia la izquierda del árbol de búsqueda binaria (BST).
Si se trata de una cola de prioridad descendente, la eliminación del elemento con la prioridad más alta se realiza mediante un recorrido hacia la derecha del árbol de búsqueda binaria (BST).

Véase también

Referencias

↑ Pitassi, Toniann (2015). "CSC263: BST balanceados, árbol AVL" (PDF) . Universidad de Toronto , Departamento de Ciencias de la Computación. pág. 6. Archivado (PDF) del original el 14 de febrero de 2019. Recuperado el 19 de mayo de 2022 .
↑ Myers, Andrew. "CS 312 Lecture: AVL Trees" . Universidad de Cornell , Departamento de Ciencias de la Computación. Archivado del original el 27 de abril de 2021. Recuperado el 19 de mayo de 2022 .
↑ Adelson-Velsky, Georgy; Landis, Evgenii (1962). "Un algoritmo para la organización de la información". Actas de la Academia de Ciencias de la URSS (en ruso). 146 : 263–266 .Traducción al inglés de Myron J. Ricci en Soviet Mathematics - Doklady , 3:1259–1263, 1962.
1 2 Culberson, J.; Munro, JI (1 de enero de 1989). "Explicando el comportamiento de los árboles de búsqueda binaria bajo actualizaciones prolongadas: un modelo y simulaciones" . The Computer Journal . 32 (1): 68– 69. doi : 10.1093/comjnl/32.1.68 .
↑ Culberson, J.; Munro, JI (28 de julio de 1986). "Análisis de los algoritmos de eliminación estándar en árboles de búsqueda binaria de dominio de ajuste exacto" . Algorithmica . 5 ( 1–4 ). Springer Publishing , Universidad de Waterloo : 297. doi : 10.1007/BF01840390 . S2CID 971813 .
↑ PF Windley (1 de enero de 1960). "Árboles, bosques y reorganización" . The Computer Journal . 3 (2): 84. doi : 10.1093/comjnl/3.2.84 .
1 2 Knuth, Donald (1998). «Sección 6.2.3: Árboles equilibrados». El arte de la programación informática (PDF) . Vol. 3 (2.ª ed.). Addison-Wesley . págs. 458–481 . ISBN 978-0201896855Archivado (PDF) del original el 09/10/2022 .
↑ Paul E. Black, "árbol rojo-negro", en Diccionario de algoritmos y estructuras de datos [en línea], Paul E. Black, ed. 12 de noviembre de 2019. (consultado el 19 de mayo de 2022) de: https://www.nist.gov/dads/HTML/redblack.html
1 2 Thareja, Reema (13 de octubre de 2018). "Hashing y colisión". Estructuras de datos usando C (2.ª ed.). Oxford University Press . ISBN 9780198099307.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). Introducción a los algoritmos (2ª ed.). Prensa del MIT . ISBN 0-262-03293-7.
↑ RA Frost; MM Peterson (1 de febrero de 1982). "Una breve nota sobre árboles de búsqueda binaria" . The Computer Journal . 25 (1). Oxford University Press : 158. doi : 10.1093/comjnl/25.1.158 .
↑ Junzhou Huang. "Diseño y análisis de algoritmos" (PDF) . Universidad de Texas en Arlington . pág. 12. Archivado (PDF) del original el 13 de abril de 2021. Recuperado el 17 de mayo de 2021 .
↑ Ray, Ray. "Árbol de búsqueda binaria" . Universidad Loyola Marymount , Departamento de Ciencias de la Computación . Recuperado el 17 de mayo de 2022 .
↑ Thornton, Alex (2021). "ICS 46: Árboles de búsqueda binaria" . Universidad de California, Irvine . Archivado del original el 4 de julio de 2021. Recuperado el 21 de octubre de 2021 .
1 2 3 4 5 Brass, Peter (enero de 2011). Estructura de datos avanzada . Cambridge University Press . doi : 10.1017/CBO9780511800191 . ISBN 9780511800191.
↑ Blum, Norbert; Mehlhorn, Kurt (1978). "Sobre el número promedio de operaciones de reequilibrio en árboles con ponderación equilibrada" (PDF) . Theoretical Computer Science . 11 (3): 303– 320. doi : 10.1016/0304-3975(80)90018-3 . Archivado (PDF) del original el 9 de octubre de 2022.
↑ Lehman, Tobin J.; Carey, Michael J. (25–28 de agosto de 1986). Un estudio de estructuras de índices para sistemas de gestión de bases de datos en memoria principal . Duodécima Conferencia Internacional sobre Bases de Datos Muy Grandes (VLDB 1986). Kioto. ISBN 0-934613-18-4.
↑ Aragon, Cecilia R.; Seidel, Raimund (1989), "Árboles de búsqueda aleatorios" (PDF) , 30.º Simposio anual sobre fundamentos de la informática , Washington, DC: IEEE Computer Society Press, pp. 540–545 , doi : 10.1109/SFCS.1989.63531 , ISBN 0-8186-1982-1, archivado (PDF) del original el 09/10/2022
↑Cormen, Thomas H.; Leiserson , Charles E.; Rivest , Ronald L .; Stein, Clifford (2001). « Árboles rojo - negro». Introducción a los algoritmos (segunda edición). MIT Press. págs. 273-301 . ISBN 978-0-262-03293-3.
↑ Comer, Douglas (junio de 1979), "El árbol B ubicuo", Computing Surveys , 11 (2): 123–137 , doi : 10.1145/356770.356776 , ISSN 0360-0300 , S2CID 101673
↑ Knuth, Donald E. (1998). "6.2.4". El arte de la programación informática . Vol. 3 (2.ª ed.). Addison Wesley. ISBN 9780201896855. Los 2-3 árboles definidos al final de la Sección 6.2.3 son equivalentes a árboles B de orden 3.
↑ Sleator, Daniel D. ; Tarjan, Robert E. (1985). "Árboles de búsqueda binaria autoajustables" (PDF) . Journal of the ACM . 32 (3): 652– 686. doi : 10.1145/3828.3835 . S2CID 1165848 .
↑ Narayanan, Arvind (2019). "COS226: Árboles de búsqueda binaria" . Escuela de Ingeniería y Ciencias Aplicadas de la Universidad de Princeton . Archivado del original el 22 de marzo de 2021. Recuperado el 21 de octubre de 2021 a través de cs.princeton.edu.
↑ Xiong, Li. "Una conexión entre los árboles de búsqueda binaria y Quicksort" . Oxford College de la Universidad de Emory , Departamento de Matemáticas e Informática. Archivado del original el 26 de febrero de 2021. Consultado el 4 de junio de 2022 .
↑ Myers, Andrew. "Apuntes de clase y tutoría de CS 2112: Colas de prioridad y montículos" . Universidad de Cornell , Departamento de Ciencias de la Computación . Archivado del original el 21 de octubre de 2021. Consultado el 21 de octubre de 2021 .

Lecturas adicionales

Este artículo incorpora material de dominio público de Paul E. Black. "Árbol de búsqueda binaria" . Diccionario de algoritmos y estructuras de datos . NIST .
Cormen, Thomas H.; Leiserson , Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "12: Árboles de búsqueda binaria, 15.5: Árboles de búsqueda binaria óptimos". Introducción a los algoritmos (2.ª ed.). MIT Press . págs. 253–272 , 356–363 . ISBN 0-262-03293-7.
Jarc, Duane J. (3 de diciembre de 2005). "Recorridos de árboles binarios" . Visualizaciones interactivas de estructuras de datos . Universidad de Maryland . Archivado del original el 27 de febrero de 2014. Recuperado el 30 de abril de 2006 .
Knuth, Donald (1997). «6.2.2: Búsqueda en árboles binarios». El arte de la programación informática . Vol. 3: «Clasificación y búsqueda» (3.ª ed.). Addison-Wesley. págs. 426–458 . ISBN 0-201-89685-0.
Long, Sean. "Árbol de búsqueda binaria" ( PPT ) . Visualización de estructuras de datos y algoritmos: un enfoque basado en diapositivas de PowerPoint . SUNY Oneonta .
Parlante, Nick (2001). "Árboles binarios" . Biblioteca de Educación en Ciencias de la Computación . Universidad de Stanford . Archivado del original el 30 de enero de 2022.

Enlaces externos

Ben Pfaff: Introducción a los árboles de búsqueda binaria y a los árboles equilibrados . (PDF; 1675 kB) 2004.
Visualización de un árbol de búsqueda binaria

[1] Pitassi, Toniann (2015). "CSC263: BST balanceados, árbol AVL" (PDF) . Universidad de Toronto , Departamento de Ciencias de la Computación. pág. 6. Archivado (PDF) del original el 14 de febrero de 2019. Recuperado el 19 de mayo de 2022 .

[2] Myers, Andrew. "CS 312 Lecture: AVL Trees" . Universidad de Cornell , Departamento de Ciencias de la Computación. Archivado del original el 27 de abril de 2021. Recuperado el 19 de mayo de 2022 .

[3] Adelson-Velsky, Georgy; Landis, Evgenii (1962). "Un algoritmo para la organización de la información". Actas de la Academia de Ciencias de la URSS (en ruso). 146 : 263–266 .Traducción al inglés de Myron J. Ricci en Soviet Mathematics - Doklady , 3:1259–1263, 1962.

[computer_journal89-4] 1 2 Culberson, J.; Munro, JI (1 de enero de 1989). "Explicando el comportamiento de los árboles de búsqueda binaria bajo actualizaciones prolongadas: un modelo y simulaciones" . The Computer Journal . 32 (1): 68– 69. doi : 10.1093/comjnl/32.1.68 .

[5] Culberson, J.; Munro, JI (28 de julio de 1986). "Análisis de los algoritmos de eliminación estándar en árboles de búsqueda binaria de dominio de ajuste exacto" . Algorithmica . 5 ( 1–4 ). Springer Publishing , Universidad de Waterloo : 297. doi : 10.1007/BF01840390 . S2CID 971813 .

[windley60-6] PF Windley (1 de enero de 1960). "Árboles, bosques y reorganización" . The Computer Journal . 3 (2): 84. doi : 10.1093/comjnl/3.2.84 .

[Knuth98-7] 1 2 Knuth, Donald (1998). «Sección 6.2.3: Árboles equilibrados». El arte de la programación informática (PDF) . Vol. 3 (2.ª ed.). Addison-Wesley . págs. 458–481 . ISBN 978-0201896855Archivado (PDF) del original el 09/10/2022 .

[8] Paul E. Black, "árbol rojo-negro", en Diccionario de algoritmos y estructuras de datos [en línea], Paul E. Black, ed. 12 de noviembre de 2019. (consultado el 19 de mayo de 2022) de: https://www.nist.gov/dads/HTML/redblack.html

[reema18-9] 1 2 Thareja, Reema (13 de octubre de 2018). "Hashing y colisión". Estructuras de datos usando C (2.ª ed.). Oxford University Press . ISBN 9780198099307.

[algo_cormen-10] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). Introducción a los algoritmos (2ª ed.). Prensa del MIT . ISBN 0-262-03293-7.

[11] RA Frost; MM Peterson (1 de febrero de 1982). "Una breve nota sobre árboles de búsqueda binaria" . The Computer Journal . 25 (1). Oxford University Press : 158. doi : 10.1093/comjnl/25.1.158 .

[12] Junzhou Huang. "Diseño y análisis de algoritmos" (PDF) . Universidad de Texas en Arlington . pág. 12. Archivado (PDF) del original el 13 de abril de 2021. Recuperado el 17 de mayo de 2021 .

[13] Ray, Ray. "Árbol de búsqueda binaria" . Universidad Loyola Marymount , Departamento de Ciencias de la Computación . Recuperado el 17 de mayo de 2022 .

[14] Thornton, Alex (2021). "ICS 46: Árboles de búsqueda binaria" . Universidad de California, Irvine . Archivado del original el 4 de julio de 2021. Recuperado el 21 de octubre de 2021 .

[peter11-15] 1 2 3 4 5 Brass, Peter (enero de 2011). Estructura de datos avanzada . Cambridge University Press . doi : 10.1017/CBO9780511800191 . ISBN 9780511800191.

[16] Blum, Norbert; Mehlhorn, Kurt (1978). "Sobre el número promedio de operaciones de reequilibrio en árboles con ponderación equilibrada" (PDF) . Theoretical Computer Science . 11 (3): 303– 320. doi : 10.1016/0304-3975(80)90018-3 . Archivado (PDF) del original el 9 de octubre de 2022.

[17] Lehman, Tobin J.; Carey, Michael J. (25–28 de agosto de 1986). Un estudio de estructuras de índices para sistemas de gestión de bases de datos en memoria principal . Duodécima Conferencia Internacional sobre Bases de Datos Muy Grandes (VLDB 1986). Kioto. ISBN 0-934613-18-4.

[18] Aragon, Cecilia R.; Seidel, Raimund (1989), "Árboles de búsqueda aleatorios" (PDF) , 30.º Simposio anual sobre fundamentos de la informática , Washington, DC: IEEE Computer Society Press, pp. 540–545 , doi : 10.1109/SFCS.1989.63531 , ISBN 0-8186-1982-1, archivado (PDF) del original el 09/10/2022

[Cormen2001-19] Cormen, Thomas H.; Leiserson , Charles E.; Rivest , Ronald L .; Stein, Clifford (2001). « Árboles rojo - negro». Introducción a los algoritmos (segunda edición). MIT Press. págs. 273-301 . ISBN 978-0-262-03293-3.

[20] Comer, Douglas (junio de 1979), "El árbol B ubicuo", Computing Surveys , 11 (2): 123–137 , doi : 10.1145/356770.356776 , ISSN 0360-0300 , S2CID 101673

[21] Knuth, Donald E. (1998). "6.2.4". El arte de la programación informática . Vol. 3 (2.ª ed.). Addison Wesley. ISBN 9780201896855. Los 2-3 árboles definidos al final de la Sección 6.2.3 son equivalentes a árboles B de orden 3.

[22] Sleator, Daniel D. ; Tarjan, Robert E. (1985). "Árboles de búsqueda binaria autoajustables" (PDF) . Journal of the ACM . 32 (3): 652– 686. doi : 10.1145/3828.3835 . S2CID 1165848 .

[23] Narayanan, Arvind (2019). "COS226: Árboles de búsqueda binaria" . Escuela de Ingeniería y Ciencias Aplicadas de la Universidad de Princeton . Archivado del original el 22 de marzo de 2021. Recuperado el 21 de octubre de 2021 a través de cs.princeton.edu.

[24] Xiong, Li. "Una conexión entre los árboles de búsqueda binaria y Quicksort" . Oxford College de la Universidad de Emory , Departamento de Matemáticas e Informática. Archivado del original el 26 de febrero de 2021. Consultado el 4 de junio de 2022 .

[25] Myers, Andrew. "Apuntes de clase y tutoría de CS 2112: Colas de prioridad y montículos" . Universidad de Cornell , Departamento de Ciencias de la Computación . Archivado del original el 21 de octubre de 2021. Consultado el 21 de octubre de 2021 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]