á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 (que lleva el nombre de los inventores A delson- V elsky y Landis ) es un árbol de búsqueda binario autoequilibrado . En un árbol AVL, las alturas de los dos subárboles secundarios de cualquier nodo difieren como máximo en 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 tiempo O (log n ) tanto en el caso promedio como en el peor, donde es el número de nodos en el árbol antes de la operación. Las inserciones y eliminaciones pueden requerir que el árbol sea reequilibrado mediante una o más rotaciones de árbol . ${\displaystyle n}$

El árbol AVL lleva el nombre de 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 jamás inventada. ^[3]

Los árboles AVL a menudo se comparan con los árboles rojo-negro porque ambos admiten el mismo conjunto de operaciones y requieren tiempo para las operaciones básicas. Para aplicaciones de búsqueda intensiva, los árboles AVL son más rápidos que los árboles rojo-negro porque están más estrictamente equilibrados. ^[4] Al igual que los árboles rojo-negro, los árboles AVL tienen una altura equilibrada. En general, ambos no están equilibrados en peso ni en ningún caso ; ^[5] es decir, los nodos hermanos pueden tener números muy 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 con se llama "pesado a la izquierda", uno con se llama "pesado hacia 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 del saldo 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 ? Esto se debe a que un árbol AVL de altura contiene al menos nodos. ¿Dónde está la secuencia de Fibonacci con los valores de las semillas? ${\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 desequilibrado , pero las modificaciones deben observar y restaurar el equilibrio de altura de los subárboles.

buscando

La búsqueda de una clave específica en un árbol AVL se puede realizar de la misma manera que en cualquier árbol de búsqueda binario equilibrado o no equilibrado . ^{[8] : cap. 8} Para que la búsqueda funcione eficazmente 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 está muy cerca de h , por lo que ambas están en O(log n ) . ^{[10] : 216}

El recorrido

Como operación de sólo 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 enlace exactamente dos veces: una visita hacia abajo para ingresar al subárbol enraizado por ese nodo, 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 anterior o siguiente en tiempo constante amortizado . ^{[11] : 58} Algunos casos de exploración de estos nodos "cercanos" requieren atravesar hasta enlaces h ∝ log( n ) (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 de el subárbol derecho de la raíz; en el árbol AVL de la figura 1, navegar desde el nodo P al nodo Q situado junto a la derecha requiere 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 sigue el mismo proceso que al insertarlo en un árbol de búsqueda binaria . Si el árbol está vacío, el nodo se inserta como raíz del árbol. Si el árbol no está vacío, bajamos hasta la raíz y bajamos recursivamente por 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 hijo izquierdo o hijo derecho del nodo externo.

Después de esta inserción, si un árbol se desequilibra, sólo se desequilibran los ancestros del nodo recién insertado. Esto se debe a que sólo 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 las invariantes de los árboles AVL: esto se llama "retrazado". 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 marcado, 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 es necesaria ninguna 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 siguiente código, la rotación adecuada inmediatamente reequilibra perfectamente 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 de hijo a padre a lo largo de la ruta de la hoja insertada. Si el procedimiento anterior se aplica a los nodos a lo largo de este camino, comenzando desde la hoja, entonces cada nodo del árbol volverá a tener un factor de equilibrio de −1, 0 o 1.

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

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

Si el factor de equilibrio se vuelve temporalmente ±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 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 O(log n ) ) tiempo. ^{[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 el nodo de reemplazo disminuye la altura del árbol hijo 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. A esto se le llama "retirada".

Dado que con una sola 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 llega a ser ±2, entonces el subárbol está desequilibrado y es necesario rotarlo. (A diferencia de la inserción, donde una rotación siempre equilibra el árbol, después de eliminar, puede haber BF(Z) ≠ 0 (ver figuras 2 y 3), de modo que después de la rotación simple o doble adecuada, la altura del subárbol reequilibrado disminuye en un significado. que el árbol debe reequilibrarse nuevamente en el siguiente nivel superior.) Los distintos 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 vuelve ±1 (debe haber sido 0), lo que significa que la altura de ese subárbol permanece sin cambios.

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

Si el factor de equilibrio llega temporalmente a ±2, esto debe repararse mediante una rotación adecuada. Depende del factor de equilibrio del 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 O(log n ) ) tiempo.

Establecer operaciones y operaciones masivas

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

La función Unir en dos árboles AVL t ₁ y t ₂ y una clave k devolverá un árbol que contiene todos los elementos en t ₁ , t ₂ y 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 en uno, Join simplemente crea un nuevo nodo con el subárbol izquierdo t ₁ , la raíz k y el subárbol derecho t ₂ . De lo contrario, supongamos 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 el hijo izquierdo c , la raíz k y el hijo derecho t ₂ para reemplazar c. El nuevo nodo satisface el invariante AVL y su altura es uno mayor que c . El aumento de altura puede aumentar la altura de sus antepasados, posiblemente invalidando el invariante AVL de esos nodos. Esto se puede solucionar con una doble rotación si no es válida en el padre o una sola rotación hacia la izquierda si no es válida en la parte superior del árbol, en ambos casos restaurando la altura de cualquier nodo ancestro adicional. Por lo tanto, la unión requerirá como máximo dos rotaciones. 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, los más pequeños que la clave k y los mayores que la clave k , primero dibuje 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 de la izquierda, 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 tecla central. Según las nuevas funciones de unión, intersección o diferencia, se puede insertar o eliminar una clave o varias claves del árbol AVL. Dado que Split llama a Join pero no se ocupa directamente de los criterios de equilibrio de los árboles AVL, dicha implementación generalmente se denomina implementación "basada en combinaciones" .

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 combinaciones 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 la diferencia de altura entre dos subárboles secundarios cambia, esto puede, siempre que sea < 2, reflejarse mediante una adaptación de la información de equilibrio en el padre. 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 principal debe "reequilibrarse". Las herramientas de reparación proporcionadas son las llamadas rotaciones de árbol , porque mueven las claves sólo "verticalmente", de modo que la secuencia en orden ("horizontal") de las claves se conserva por completo (lo cual 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. Se modificó su subárbol izquierdo o derecho. Sea Z el hijo con el subárbol superior (ver figuras 2 y 3). Tenga en cuenta que ambos niños están en forma AVL según la hipótesis de inducción .

En caso de inserción, esta inserción le ha sucedido a uno de los hijos de Z de manera que la altura de Z ha aumentado. En caso de eliminación, esta eliminación le ha ocurrido al hermano t ₁ de Z de tal manera que la altura de t ₁ , que ya es más baja, ha disminuido. (Éste es el único caso en el que el factor de equilibrio de Z también puede ser 0).

Hay cuatro posibles variantes de la infracción:

Y el reequilibrio se realiza de manera diferente:

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

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

Rotación sencilla

La Figura 2 muestra una situación de Derecha Derecha. En su mitad superior, el nodo X tiene dos árboles secundarios 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 mayor que su hermano t ₄ . Esto puede suceder por un aumento de la altura del subárbol t ₄ o por una disminución de la altura del subárbol t ₁ . En el último caso, también puede ocurrir la situación pálida en la que t ₂₃ tiene la misma altura que t _{4 .}

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

Como muestra la figura, antes de una inserción, la capa foliar 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 foliar estaba en el nivel h+2, donde está nuevamente, cuando t ₂₃ y t ₄ tenían la misma altura. De lo contrario, la capa de hojas alcanza el nivel h+1, de modo que la altura del árbol rotado disminuye.

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

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

nodo * rotar_Izquierda ( nodo * X , nodo * Z ) {      // Z es 2 mayor que su hermano t23 = hijo_izquierdo ( Z ); // Niño interior de Z    niño_derecho ( X ) = t23 ;   si ( t23 ! = nulo )    padre ( t23 ) = X ;   hijo_izquierdo ( Z ) = X ;   padre ( X ) = Z ;   // 1er caso, BF(Z) == 0, // sólo ocurre con la eliminación, no con la inserción: if ( BF ( Z ) == 0 ) { // t23 ha tenido 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 ;   } devolver Z ; // devuelve la nueva raíz del subárbol rotado  }

Doble rotación

La Figura 3 muestra una situación de Derecha Izquierda. En su tercio superior, el nodo X tiene dos árboles secundarios con un factor de equilibrio de +2 . Pero a diferencia de la figura 2, el niño interior Y de Z es mayor que su hermano t ₄ . Esto puede suceder por la inserción del propio Y o por un aumento en la altura de uno de sus subárboles t ₂ o t ₃ (con la consecuencia de que son de diferente altura) o por una disminución en la altura del subárbol t ₁ . 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 actualizarán cinco enlaces (bordes gruesos en la figura 3) y tres factores de equilibrio.

Como muestra la figura, antes de una inserción, la capa foliar 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, por lo que la altura del árbol rotado disminuye.

Fig. 3: Rotación doble rotar_DerechaIzquierda ( X , Z )
= rotar_Derecha alrededor de Z seguido de
rotar_Izquierda alrededor de X

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

nodo * rotar_DerechaIzquierda ( nodo * X , nodo * Z ) {      // Z es 2 mayor que su hermano Y = hijo_izquierdo ( Z ); // Niño interior de Z    // Y es 1 mayor que el hermano t3 = hijo_derecho ( Y );   hijo_izquierdo ( Z ) = t3 ;   si ( t3 ! = nulo )    padre ( t3 ) = Z ;   niño_derecho ( Y ) = Z ;   padre ( Z ) = Y ;   t2 = hijo_izquierdo ( Y );   niño_derecho ( 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 ;   } más si ( BF ( Y ) > 0 ) {       // t3 fue mayor BF ( X ) = – 1 ; // t1 ahora más alto    BF ( Z ) = 0 ;   } demás {   // t2 fue mayor BF ( X ) = 0 ;   BF ( Z ) = + 1 ; // t4 ahora más alto    } FB ( Y ) = 0 ;   devolver Y ; // devuelve 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 de búsqueda binarios autoequilibrados y están relacionados matemáticamente. De hecho, cada árbol AVL puede colorearse de rojo a negro, ^[14] pero hay árboles RB que no están equilibrados con 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 de AVL o RB requieren inspecciones O (log n ) y/o actualizaciones de los factores de equilibrio de AVL (o colores de RB). Las inserciones y eliminaciones de RB y las inserciones de 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 de 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, es suficiente un bit con el significado "inferior a 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 eliminaciones, Ben Pfaff muestra en 79 mediciones una relación de AVL/RB entre 0,677 y 1,077 con mediana ≈0,947 y media geométrica ≈0,910. ^[4]

Ver también

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

Referencias

1. 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 Matemáticas soviéticas - Doklady , 3:1259–1263, 1962.
3. Sedgewick, Robert (1983). "Árboles equilibrados" . Algoritmos . Addison-Wesley. pag. 199.ISBN​ 0-201-06672-6.
4. Pfaff, Ben (junio de 2004). "Análisis de rendimiento de BST en software de sistema" (PDF) . Universidad Stanford .
5. Los árboles AVL no tienen un peso equilibrado? (es decir: ¿los árboles AVL no están equilibrados en μ?)
   Por lo tanto: un árbol binario se denomina 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 mantiene y es mínimo con esta propiedad. es el número de nodos debajo del árbol con 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). Clasificación y búsqueda (2. ed., 6. impresión, recién actualizado y ed. rev.). Boston [ua]: Addison-Wesley. ISBN 0-201-89685-0.
7. Sin embargo, la información del saldo se puede mantener en los nodos secundarios como un bit que indica si el padre es mayor en 1 o en 2; por lo tanto, un aumento de 2 no puede ocurrir para ambos niños. De esta manera, el árbol AVL es un árbol de "rango equilibrado" , como lo acuñaron Haeupler, Sen y Tarjan.
8. Dixit, JB (2010). Dominar las estructuras de datos a través del lenguaje 'C' . Nueva Delhi, India: University Science Press, una editorial de Laxmi Publications Pvt. Limitado. ISBN limitado 9789380386720. OCLC  939446542.
9. Brass, Peter (2008). Estructuras de datos avanzadas . Cambridge: Prensa de la Universidad de Cambridge. ISBN 9780511438202. OCLC  312435417.
10. Hubbard, John Rast (2000). Esquema de teoría y problemas de estructuras de datos con Java de Schaum . Nueva York: McGraw-Hill. ISBN 0071378707. OCLC  48139308.
11. Pfaff, Ben (2004). Introducción a los árboles de búsqueda binaria y los árboles equilibrados . Fundación de Software Libre, Inc.
12. Weiss, Mark Allen (2006). Estructuras de datos y análisis de algoritmos en C++ (3ª ed.). Boston: Pearson Addison-Wesley. pag. 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 arquitecturas y algoritmos paralelos , ACM, págs. 253–264, arXiv : 1602.02120 , doi : 10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID  2897793.
14. Paul E. Negro (13 de abril de 2015). "Árbol AVL". Diccionario de Algoritmos y Estructuras de Datos . Instituto Nacional de Estándares y Tecnología . Consultado el 2 de julio de 2016 .
15. Mehlhorn, Kurt; Lijadoras, Peter (2008). Algoritmos y estructuras de datos. Berlín, Heidelberg: Springer Berlín Heidelberg. doi :10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
16. Dinesh P. Mehta; Sartaj Sahni, eds. (2017-12-15). Manual de estructuras y aplicaciones de datos (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

Otras lecturas

• Donald Knuth . El arte de la programación informática , volumen 3: clasificació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 de rango equilibrado" (PDF) , Transacciones ACM sobre algoritmos , 11 (4): art. 30, 26, doi :10.1145/2689412, SEÑOR  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 .