Árbol AVL

Árbol de búsqueda binario autoequilibrado

Animación que muestra la inserción de varios elementos en un árbol AVL. Incluye rotaciones izquierda, derecha, izquierda-derecha y derecha-izquierda.

Fig. 1: Árbol AVL con factores de equilibrio (verde)

En informática , un árbol AVL (llamado así por los inventores A delson -V elsky y Landis ) es un árbol binario de búsqueda autoequilibrado . En un árbol AVL, las alturas de los dos subárboles secundarios de cualquier nodo difieren en como máximo uno; si en algún momento difieren en más de uno, se realiza un reequilibrio para restaurar esta propiedad. La búsqueda, la inserción y la eliminación toman un tiempo de O (log n ) tanto en el caso promedio como en el peor de los casos, donde es el número de nodos en el árbol antes de la operación. Las inserciones y eliminaciones pueden requerir que el árbol se reequilibre mediante una o más rotaciones de árbol . ${\displaystyle n}$

El árbol AVL debe su nombre a sus dos inventores soviéticos , Georgy Adelson-Velsky y Evgenii Landis , quienes lo publicaron en su artículo de 1962 "Un algoritmo para la organización de la información". ^{[2] Es la} estructura de datos de árbol de búsqueda binaria autoequilibrada más antigua que se haya inventado. ^[3]

Los árboles AVL suelen compararse con los árboles rojo-negros porque ambos admiten el mismo conjunto de operaciones y requieren tiempo para las operaciones básicas. Para aplicaciones con búsquedas intensivas, los árboles AVL son más rápidos que los árboles rojo-negros porque están más estrictamente equilibrados. ^[4] De manera similar a los árboles rojo-negros, los árboles AVL están equilibrados en altura. Ambos, en general, no están equilibrados en peso ni en - para ningún ; ^[5] es decir, los nodos hermanos pueden tener cantidades enormemente diferentes de descendientes. ${\displaystyle {\text{O}}(\log n)}$ ${\displaystyle \mu }$ ${\displaystyle \mu \leq {\tfrac {1}{2}}}$

Definición

Factor de equilibrio

En un árbol binario, el factor de equilibrio de un nodo X se define como la diferencia de altura.

${\displaystyle {\text{BF}}(X):={\text{Height}}({\text{RightSubtree}}(X))-{\text{Height}}({\text{LeftSubtree}}(X))}$^{[6] : 459}

de sus dos subárboles secundarios enraizados en el nodo X.

Un nodo X se llama "pesado a la izquierda", uno con se llama "pesado a la derecha" y uno con a veces simplemente se llama "equilibrado". ${\displaystyle {\text{BF}}(X)<0}$ ${\displaystyle {\text{BF}}(X)>0}$ ${\displaystyle {\text{BF}}(X)=0}$

Propiedades

Los factores de equilibrio se pueden mantener actualizados conociendo los factores de equilibrio anteriores y el cambio de altura; no es necesario conocer la altura absoluta. Para mantener la información de equilibrio de AVL, son suficientes dos bits por nodo. ^[7]

La altura (contada como el número máximo de niveles) de un árbol AVL con nodos se encuentra en el intervalo: ^{[6] : 460} ${\displaystyle h}$ ${\displaystyle n}$

${\displaystyle \log _{2}(n+1)\leq h<\log _{\varphi }(n+2)+b}$

¿Dónde   está la proporción áurea y Esto se debe a que un árbol AVL de altura contiene al menos nodos donde está la secuencia de Fibonacci con los valores semilla? ${\displaystyle \varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618}$ ${\displaystyle b:={\frac {\log _{2}5}{2\log _{2}\varphi }}-2\approx \;-0.3277.}$ ${\displaystyle h}$ ${\displaystyle F_{h+2}-1}$ ${\displaystyle \{F_{n}\}_{n\in \mathbb {N} }}$ ${\displaystyle F_{1}=F_{2}=1.}$

Operaciones

Las operaciones de solo lectura de un árbol AVL implican realizar las mismas acciones que se llevarían a cabo en un árbol de búsqueda binario no balanceado , pero las modificaciones deben observar y restaurar el equilibrio de altura de los subárboles.

Búsqueda

La búsqueda de una clave específica en un árbol AVL se puede realizar de la misma manera que la de cualquier árbol de búsqueda binario balanceado o no balanceado . ^{[8] : cap. 8} Para que la búsqueda funcione de manera efectiva, debe emplear una función de comparación que establezca un orden total (o al menos un preorden total ) en el conjunto de claves. ^{[9] : 23} El número de comparaciones necesarias para una búsqueda exitosa está limitado por la altura h y para una búsqueda fallida es muy cercano a h , por lo que ambos están en O(log n ) . ^{[10] : 216}

Travesía

Como operación de solo lectura, el recorrido de un árbol AVL funciona de la misma manera que en cualquier otro árbol binario. Al explorar los n nodos del árbol, se visita cada vínculo exactamente dos veces: una visita hacia abajo para ingresar al subárbol cuya raíz es ese nodo, y otra visita hacia arriba para abandonar el subárbol de ese nodo después de haberlo explorado.

Una vez que se ha encontrado un nodo en un árbol AVL, se puede acceder al nodo siguiente o anterior en tiempo constante amortizado . ^{[11] : 58} Algunas instancias de exploración de estos nodos "cercanos" requieren atravesar hasta h ∝ log( n ) enlaces (particularmente cuando se navega desde la hoja más a la derecha del subárbol izquierdo de la raíz hasta la raíz o desde la raíz hasta la hoja más a la izquierda del subárbol derecho de la raíz; en el árbol AVL de la figura 1, navegar desde el nodo P hasta el nodo siguiente a la derecha Q lleva 3 pasos). Dado que hay n −1 enlaces en cualquier árbol, el costo amortizado es 2×( n −1)/ n , o aproximadamente 2.

Insertar

Al insertar un nodo en un árbol AVL, inicialmente se sigue el mismo proceso que al insertarlo en un árbol de búsqueda binaria . Si el árbol está vacío, entonces el nodo se inserta como la raíz del árbol. Si el árbol no está vacío, entonces bajamos por la raíz y recorremos recursivamente el árbol buscando la ubicación para insertar el nuevo nodo. Este recorrido está guiado por la función de comparación. En este caso, el nodo siempre reemplaza una referencia NULL (izquierda o derecha) de un nodo externo en el árbol, es decir, el nodo se convierte en un hijo izquierdo o un hijo derecho del nodo externo.

Después de esta inserción, si un árbol se desequilibra, solo los ancestros del nodo recién insertado se desequilibran. Esto se debe a que solo esos nodos tienen sus subárboles alterados. ^[12] Por lo tanto, es necesario verificar la coherencia de cada uno de los ancestros del nodo con los invariantes de los árboles AVL: esto se llama "retracing". Esto se logra considerando el factor de equilibrio de cada nodo. ^{[6] : 458–481  [11] : 108}

Dado que con una sola inserción la altura de un subárbol AVL no puede aumentar en más de uno, el factor de equilibrio temporal de un nodo después de una inserción estará en el rango [–2,+2]. Para cada nodo verificado, si el factor de equilibrio temporal permanece en el rango de –1 a +1, entonces solo es necesaria una actualización del factor de equilibrio y no una rotación. Sin embargo, si el factor de equilibrio temporal es ±2, el subárbol enraizado en este nodo está desequilibrado AVL y se necesita una rotación. ^{[9] : 52} Con la inserción como muestra el código a continuación, la rotación adecuada reequilibra perfectamente de inmediato el árbol.

En la figura 1, al insertar el nuevo nodo Z como hijo del nodo X, la altura de ese subárbol Z aumenta de 0 a 1.

Invariante del bucle de retroceso para una inserción

La altura del subárbol enraizado por Z ha aumentado en 1. Ya tiene forma AVL.

Para actualizar los factores de equilibrio de todos los nodos, primero observe que todos los nodos que requieren corrección se encuentran desde el nodo hijo al nodo padre a lo largo de la ruta de la hoja insertada. Si el procedimiento anterior se aplica a los nodos a lo largo de esta ruta, comenzando desde la hoja, entonces cada nodo en el árbol volverá a tener un factor de equilibrio de -1, 0 o 1.

El retroceso puede detenerse si el factor de equilibrio llega a ser 0, lo que implica que la altura de ese subárbol permanece sin cambios.

Si el factor de equilibrio se convierte en ±1, entonces la altura del subárbol aumenta en uno y el retroceso debe continuar.

Si el factor de equilibrio se convierte temporalmente en ±2, esto debe repararse mediante una rotación adecuada después de la cual el subárbol tiene la misma altura que antes (y su raíz es el factor de equilibrio 0).

El tiempo requerido es O(log n ) para la búsqueda, más un máximo de O(log n ) niveles de retroceso ( O(1) en promedio) en el camino de regreso a la raíz, por lo que la operación se puede completar en un tiempo O(log n ) . ^{[9] : 53}

Borrar

Los pasos preliminares para eliminar un nodo se describen en la sección Árbol de búsqueda binaria#Eliminación . Allí, la eliminación efectiva del nodo sujeto o del nodo de reemplazo disminuye la altura del árbol secundario correspondiente de 1 a 0 o de 2 a 1, si ese nodo tenía un hijo.

A partir de este subárbol, es necesario comprobar la coherencia de cada uno de los ancestros con las invariantes de los árboles AVL. Esto se denomina "retroceso".

Dado que con una única eliminación la altura de un subárbol AVL no puede disminuir en más de uno, el factor de equilibrio temporal de un nodo estará en el rango de −2 a +2. Si el factor de equilibrio permanece en el rango de −1 a +1, se puede ajustar de acuerdo con las reglas AVL. Si se convierte en ±2, el subárbol está desequilibrado y necesita ser rotado. (A diferencia de la inserción, donde una rotación siempre equilibra el árbol, después de la eliminación, puede haber BF(Z) ≠ 0 (ver figuras 2 y 3), de modo que después de la rotación simple o doble apropiada, la altura del subárbol reequilibrado disminuye en uno, lo que significa que el árbol debe ser reequilibrado nuevamente en el siguiente nivel superior). Los diversos casos de rotaciones se describen en la sección Reequilibrio.

Invariante del bucle de retroceso para una eliminación

La altura del subárbol enraizado por N ha disminuido en 1. Ya tiene forma AVL.

El retroceso puede detenerse si el factor de equilibrio se convierte en ±1 (debe haber sido 0), lo que significa que la altura de ese subárbol permanece sin cambios.

Si el factor de equilibrio se convierte en 0 (debe haber sido ±1), entonces la altura del subárbol disminuye en uno y el retroceso debe continuar.

Si el factor de equilibrio se convierte temporalmente en ±2, esto debe repararse mediante una rotación adecuada. Depende del factor de equilibrio del árbol hermano Z (el árbol hijo superior en la figura 2) si la altura del subárbol disminuye en uno (y el retroceso debe continuar) o no cambia (si Z tiene el factor de equilibrio 0) y todo el árbol tiene forma AVL.

El tiempo requerido es O(log n ) para la búsqueda, más un máximo de O(log n ) niveles de retroceso ( O(1) en promedio) en el camino de regreso a la raíz, por lo que la operación se puede completar en un tiempo O(log n ) .

Operaciones de conjunto y operaciones en masa

Además de las operaciones de inserción, eliminación y búsqueda de un solo elemento, se han definido varias operaciones de conjunto en los árboles AVL: unión , intersección y diferencia de conjuntos . A continuación, se pueden implementar operaciones rápidas en bloque sobre inserciones o eliminaciones basadas en estas funciones de conjunto. Estas operaciones de conjunto se basan en dos operaciones auxiliares, Split y Join . Con las nuevas operaciones, la implementación de los árboles AVL puede ser más eficiente y altamente paralelizable. ^[13]

La función Join en dos árboles AVL t ₁ y t ₂ y una clave k devolverá un árbol que contiene todos los elementos en t ₁ , t ₂ así como k . Requiere que k sea mayor que todas las claves en t ₁ y menor que todas las claves en t ₂ . Si los dos árboles difieren en altura como máximo uno, Join simplemente crea un nuevo nodo con subárbol izquierdo t ₁ , raíz k y subárbol derecho t ₂ . De lo contrario, suponga que t ₁ es mayor que t ₂ para más de uno (el otro caso es simétrico). Join sigue la columna derecha de t ₁ hasta un nodo c que está equilibrado con t ₂ . En este punto, se crea un nuevo nodo con hijo izquierdo c , raíz k e hijo derecho t ₂ para reemplazar a c. El nuevo nodo satisface el invariante AVL y su altura es uno mayor que c . El aumento en la altura puede aumentar la altura de sus antecesores, posiblemente invalidando el invariante AVL de esos nodos. Esto se puede solucionar con una doble rotación si no es válido en el árbol padre o con una única rotación a la izquierda si no es válido en los nodos superiores del árbol. En ambos casos, se restaura la altura para cualquier nodo ancestro posterior. Por lo tanto, la unión requerirá dos rotaciones como máximo. El costo de esta función es la diferencia de alturas entre los dos árboles de entrada.

Para dividir un árbol AVL en dos árboles más pequeños, aquellos más pequeños que la clave k y aquellos mayores que la clave k , primero se dibuja una ruta desde la raíz insertando k en el AVL. Después de esta inserción, todos los valores menores que k se encontrarán a la izquierda de la ruta, y todos los valores mayores que k se encontrarán a la derecha. Al aplicar Join , todos los subárboles del lado izquierdo se fusionan de abajo hacia arriba usando claves en la ruta como nodos intermedios de abajo hacia arriba para formar el árbol izquierdo, y la parte derecha es asimétrica. El costo de Split es O(log n ) , orden de la altura del árbol.

La unión de dos árboles AVL t ₁ y t ₂ que representan los conjuntos A y B , es un AVL t que representa A ∪ B .

El algoritmo para la intersección o diferencia es similar, pero requiere la rutina auxiliar Join2 que es la misma que Join pero sin la clave intermedia. Según las nuevas funciones para la unión, intersección o diferencia, se puede insertar o eliminar una o varias claves en el árbol AVL. Dado que Split llama a Join pero no se ocupa directamente de los criterios de equilibrio de los árboles AVL, este tipo de implementación suele denominarse implementación "basada en unión" .

La complejidad de cada unión, intersección y diferencia es para árboles AVL de tamaños y . Más importante aún, dado que las llamadas recursivas a unión, intersección o diferencia son independientes entre sí, se pueden ejecutar en paralelo con una profundidad paralela . ^[13] Cuando , la implementación basada en unión tiene el mismo DAG computacional que la inserción y eliminación de un solo elemento. ${\displaystyle {\text{O}}\left(m\log \left({n \over m}+1\right)\right)}$ ${\displaystyle m}$ ${\displaystyle n\;(\geq m)}$ ${\displaystyle {\text{O}}(\log m\log n)}$ ${\displaystyle m=1}$

Reequilibrio

Si durante una operación de modificación cambia la diferencia de altura entre dos subárboles secundarios, esto puede reflejarse, siempre que sea < 2, en una adaptación de la información de equilibrio en el árbol primario. Durante las operaciones de inserción y eliminación puede surgir una diferencia de altura (temporal) de 2, lo que significa que el subárbol primario debe ser "reequilibrado". Las herramientas de reparación dadas son las llamadas rotaciones de árboles , porque mueven las claves solo "verticalmente", de modo que la secuencia en orden ("horizontal") de las claves se conserva por completo (lo que es esencial para un árbol de búsqueda binaria). ^{[6] : 458–481  [11] : 33}

Sea X el nodo que tiene un factor de equilibrio (temporal) de −2 o +2. Su subárbol izquierdo o derecho fue modificado. Sea Z el hijo con el subárbol superior (ver figuras 2 y 3). Nótese que ambos hijos tienen forma AVL por hipótesis de inducción .

En caso de inserción, esta inserción se ha producido en uno de los hijos de Z, de forma que la altura de Z ha aumentado. En caso de eliminación, esta eliminación se ha producido en el hermano t ₁ de Z, de forma que la altura de t ₁ , que ya era menor, ha disminuido. (Este es el único caso en el que el factor de equilibrio de Z también puede ser 0).

Existen cuatro posibles variantes de la infracción:

Y el reequilibrio se realiza de forma diferente:

Por lo tanto, las situaciones se denotan como CB , donde C (= dirección del hijo) y B (= equilibrio) provienen del conjunto { Izquierda , Derecha } con Derecha  := − Izquierda . La violación del equilibrio del caso C == B se repara con una simple rotación rotate_(− C ), mientras que el caso C  != B se repara con una doble rotación rotate_CB .

El costo de una rotación, ya sea simple o doble, es constante.

Rotación simple

La figura 2 muestra una situación Derecha Derecha. En su mitad superior, el nodo X tiene dos árboles hijos con un factor de equilibrio de +2 . Además, el hijo interno t ₂₃ de Z (es decir, hijo izquierdo cuando Z es hijo derecho, o hijo derecho cuando Z es hijo izquierdo) no es más alto que su hermano t _4. Esto puede suceder por un aumento de altura del subárbol t ₄ o por una disminución de altura del subárbol t _1. En el último caso, también puede ocurrir la situación pálida donde t ₂₃ tiene la misma altura que t ₄ .

El resultado de la rotación a la izquierda se muestra en la mitad inferior de la figura. Se deben actualizar tres enlaces (bordes gruesos en la figura 2) y dos factores de equilibrio.

Como muestra la figura, antes de una inserción, la capa de hojas estaba en el nivel h+1, temporalmente en el nivel h+2 y después de la rotación nuevamente en el nivel h+1. En caso de una eliminación, la capa de hojas estaba en el nivel h+2, donde está nuevamente, cuando t ₂₃ y t ₄ tenían la misma altura. En caso contrario, la capa de hojas alcanza el nivel h+1, por lo que la altura del árbol rotado disminuye.

Fig. 2: Rotación simple
rotate_Left ( X , Z )

Fragmento de código de una rotación simple hacia la izquierda

nodo * rotar_izquierda ( nodo * X , nodo * Z ) {      // Z es 2 veces mayor que su hermano t23 = hijo_izquierdo ( Z ); // Hijo interno de Z    derecho_hijo ( X ) = t23 ;   si ( t23 != nulo )    padre ( t23 ) = X ;   hijo_izquierdo ( Z ) = X ;   padre ( X ) = Z ;   // 1er caso, BF(Z) == 0, // solo ocurre con la eliminación, no con la inserción: si ( BF ( Z ) == 0 ) { //t23 tiene la misma altura que t4      BF ( X ) = + 1 ; // t23 ahora más alto    BF ( Z ) = – 1 ; // t4 ahora es menor que X    } demás  { // El segundo caso ocurre con la inserción o eliminación:  BF ( X ) = 0 ;   BF ( Z ) = 0 ;   } retorna Z ; // retorna la nueva raíz del subárbol rotado  }

Doble rotación

La figura 3 muestra una situación Derecha-Izquierda. En su tercio superior, el nodo X tiene dos árboles hijos con un factor de equilibrio de +2 . Pero a diferencia de la figura 2, el hijo interno Y de Z es más alto que su hermano t _4. Esto puede suceder por la inserción del propio Y o por un aumento de altura de uno de sus subárboles t ₂ o t ₃ (con la consecuencia de que sean de diferente altura) o por una disminución de altura del subárbol t _1. En este último caso, también puede ocurrir que t ₂ y t ₃ tengan la misma altura.

El resultado de la primera rotación, la derecha, se muestra en el tercio medio de la figura. (Con respecto a los factores de equilibrio, esta rotación no es del mismo tipo que las otras rotaciones simples de AVL, porque la diferencia de altura entre Y y t ₄ es solo 1). El resultado de la rotación final hacia la izquierda se muestra en el tercio inferior de la figura. Se deben actualizar cinco enlaces (bordes gruesos en la figura 3) y tres factores de equilibrio.

Como muestra la figura, antes de una inserción, la capa de hojas estaba en el nivel h+1, temporalmente en el nivel h+2 y después de la doble rotación nuevamente en el nivel h+1. En caso de una eliminación, la capa de hojas estaba en el nivel h+2 y después de la doble rotación está en el nivel h+1, de modo que la altura del árbol rotado disminuye.

Fig. 3: Doble rotación rotate_RightLeft ( X , Z )
= rotate_Right alrededor de Z seguido de
rotate_Left alrededor de X

Fragmento de código de una doble rotación derecha-izquierda

nodo * rotar_DerechaIzquierda ( nodo * X , nodo * Z ) {      // Z es 2 veces mayor que su hermano Y = hijo_izquierdo ( Z ); // Hijo interno de Z    // Y es 1 más alto que su hermano t3 = hijo_derecho ( Y );   hijo_izquierdo ( Z ) = t3 ;   si ( t3 != nulo )    padre ( t3 ) = Z ;   derecho_hijo ( Y ) = Z ;   padre ( Z ) = Y ;   t2 = hijo_izquierdo ( Y );   derecho_hijo ( X ) = t2 ;   si ( t2 != nulo )    padre ( t2 ) = X ;   hijo_izquierdo ( Y ) = X ;   padre ( X ) = Y ;   // 1er caso, BF(Y) == 0 si ( BF ( Y ) == 0 ) {     BF ( X ) = 0 ;   BF ( Z ) = 0 ;   } de lo contrario si ( BF ( Y ) > 0 ) {       // t3 era más alto BF ( X ) = – 1 ; // t1 ahora es mayor    BF ( Z ) = 0 ;   } demás {   // t2 era mayor BF ( X ) = 0 ;   BF ( Z ) = + 1 ; // t4 ahora es más alto    } BF ( Y ) = 0 ;   retorna Y ; // retorna la nueva raíz del subárbol rotado  }

Comparación con otras estructuras

Tanto los árboles AVL como los árboles rojo-negro (RB) son árboles binarios de búsqueda autoequilibrados y están relacionados matemáticamente. De hecho, cada árbol AVL puede colorearse de rojo-negro, ^[14] pero hay árboles RB que no están equilibrados AVL. Para mantener las invariantes del árbol AVL (o RB), las rotaciones juegan un papel importante. En el peor de los casos, incluso sin rotaciones, las inserciones o eliminaciones AVL o RB requieren inspecciones O(log n ) y/o actualizaciones de los factores de equilibrio AVL (o colores RB). Las inserciones y eliminaciones RB y las inserciones AVL requieren de cero a tres rotaciones recursivas de cola y se ejecutan en tiempo O(1) amortizado , ^{[15] : pp.165, 158  [16]} por lo tanto igualmente constantes en promedio. Las eliminaciones AVL que requieren rotaciones O(log n ) en el peor de los casos también son O(1) en promedio. Los árboles RB requieren almacenar un bit de información (el color) en cada nodo, mientras que los árboles AVL utilizan principalmente dos bits para el factor de equilibrio, aunque, cuando se almacenan en los hijos, basta con un bit que signifique «inferior al hermano». La mayor diferencia entre las dos estructuras de datos es su límite de altura.

Para un árbol de tamaño n ≥ 1

• La altura de un árbol AVL es como máximo

  ${\displaystyle {\begin{array}{ll}h&\leqq \;c\log _{2}(n+d)+b\\&<\;c\log _{2}(n+2)+b\end{array}}}$

donde   la proporción áurea , y  . ${\displaystyle \varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618}$ ${\displaystyle c:={\tfrac {1}{\log _{2}\varphi }}\approx 1.440,}$   ${\displaystyle b:={\tfrac {c}{2}}\log _{2}5-2\approx \;-0.328,}$ ${\displaystyle d:=1+{\tfrac {1}{\varphi ^{4}{\sqrt {5}}}}\approx 1.065}$

• La altura de un árbol RB es como máximo

  ${\displaystyle {\begin{array}{ll}h&\leqq \;2\log _{2}(n+1)\end{array}}}$ . ^[17]

Los árboles AVL están más rígidamente equilibrados que los árboles RB con una relación asintótica AVL/RB ≈0,720 de las alturas máximas. Para inserciones y deleciones, Ben Pfaff muestra en 79 mediciones una relación de AVL/RB entre 0,677 y 1,077 con una mediana ≈0,947 y una media geométrica ≈0,910. ^[4]

Véase también

• Árbol WAVL
• Árbol de peso equilibrado
• Árbol de expansión
• Árbol del chivo expiatorio
• Árbol B
• árbol T
• Lista de estructuras de datos

Referencias

1. Eric Alexander. «Árboles AVL». Archivado desde el original el 31 de julio de 2019.
2. 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.
3. Sedgewick, Robert (1983). "Árboles equilibrados" . Algoritmos . Addison-Wesley. pág. 199. ISBN. 0-201-06672-6.
4. Pfaff, Ben (junio de 2004). "Análisis de rendimiento de BST en software de sistemas" (PDF) . Universidad de Stanford .
5. Los árboles AVL no están equilibrados en peso? (es decir: ¿los árboles AVL no están equilibrados en μ?)
   Por lo tanto: Un árbol binario se llama equilibrado, con , si para cada nodo , la desigualdad ${\displaystyle \mu }$ ${\displaystyle 0\leq \mu \leq {\tfrac {1}{2}}}$ ${\displaystyle N}$

   ${\displaystyle {\tfrac {1}{2}}-\mu \leq {\tfrac {|N_{l}|}{|N|+1}}\leq {\tfrac {1}{2}}+\mu }$

   se cumple y es mínimo con esta propiedad. es el número de nodos debajo del árbol con como raíz (incluida la raíz) y es el nodo secundario izquierdo de . ${\displaystyle \mu }$ ${\displaystyle |N|}$ ${\displaystyle N}$ ${\displaystyle N_{l}}$ ${\displaystyle N}$
6. Knuth, Donald E. (2000). Ordenación y búsqueda (2.ª ed., 6.ª edición, nueva edición actualizada y revisada). Boston [ua]: Addison-Wesley. ISBN 0-201-89685-0.
7. Sin embargo, la información de equilibrio se puede mantener en los nodos secundarios como un bit que indica si el padre es superior en 1 o en 2; por lo tanto, no puede ocurrir que ambos hijos sean superiores en 2. De esta manera, el árbol AVL es un árbol "equilibrado por rango" , como lo denominaron Haeupler, Sen y Tarjan.
8. Dixit, JB (2010). Dominar las estructuras de datos mediante el lenguaje "C" . Nueva Delhi, India: University Science Press, una editorial de Laxmi Publications Pvt. Ltd. ISBN 9789380386720.OCLC 939446542  .
9. Brass, Peter (2008). Estructuras de datos avanzadas . Cambridge: Cambridge University Press. ISBN 9780511438202.OCLC 312435417  .
10. Hubbard, John Rast (2000). Esquema de Schaum sobre la teoría y los problemas de las estructuras de datos con Java . Nueva York: McGraw-Hill. ISBN 0071378707.OCLC 48139308  .
11. Pfaff, Ben (2004). Introducción a los árboles binarios de búsqueda y árboles equilibrados . Free Software Foundation, Inc.
12. Weiss, Mark Allen (2006). Estructuras de datos y análisis de algoritmos en C++ (3.ª ed.). Boston: Pearson Addison-Wesley. pág. 145. ISBN 0-321-37531-9.OCLC 61278554  .
13. Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Simplemente únase para conjuntos ordenados paralelos", Simposio sobre algoritmos y arquitecturas paralelas , ACM, págs. 253–264, arXiv : 1602.02120 , doi :10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, Número de identificación del sujeto  2897793.
14. Paul E. Black (13 de abril de 2015). «Árbol AVL». Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Normas y Tecnología . Consultado el 2 de julio de 2016 .
15. Mehlhorn, Kurt; Sanders, Peter (2008). Algoritmos y estructuras de datos. Berlín, Heidelberg: Springer Berlin Heidelberg. doi :10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
16. Dinesh P. Mehta; Sartaj Sahni, eds. (15 de diciembre de 2017). Manual de estructuras de datos y aplicaciones (2.ª ed.). Nueva York: Chapman y Hall/CRC. doi :10.1201/9781315119335. ISBN 978-1-315-11933-5.
17. Árbol rojo-negro#Prueba de límites

Lectura adicional

• Donald Knuth . The Art of Computer Programming , Volumen 3: Ordenación y búsqueda , Tercera edición. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Páginas 458–475 de la sección 6.2.3: Árboles equilibrados. 
• Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2015), "Árboles con equilibrio de rango" (PDF) , ACM Transactions on Algorithms , 11 (4): Art. 30, 26, doi :10.1145/2689412, MR  3361215, S2CID  1407290.

Enlaces externos

•  Este artículo incorpora material de dominio público de Paul E. Black. "Árbol AVL". Diccionario de algoritmos y estructuras de datos . NIST .