Árbol AVL

Tipo

árbol

Inventado

1962

Inventado por

Complejidad del tiempo en notación O grande

Algoritmo	Promedio	Peor de los casos
Espacio	${\text{O}}(n)$	${\text{O}}(n)$
Buscar	${\text{O}}(\log n)$ ^[1]	${\text{O}}(\log n)$ ^[1]
Insertar	${\text{O}}(\log n)$ ^[1]	${\text{O}}(\log n)$ ^[1]
Borrar	${\text{O}}(\log n)$ ^[1]	${\text{O}}(\log n)$ ^[1]

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 L andis) es un árbol de búsqueda binaria autoequilibrado . Fue la primera estructura de datos de este tipo que se inventó. ^[2] 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, inserción y eliminación toman $O (log n)$ tiempo tanto en el promedio como en el peor de los casos, donde $n$ 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 .

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". ^[3]

Los árboles AVL a menudo se comparan con árboles rojo-negro porque ambos soportan el mismo conjunto de operaciones y toman 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. Ambos son, en general, ni equilibrada de peso ni -balanced para cualquier ; ^[5] es decir, los nodos hermanos pueden tener un número enormemente diferente de descendientes. ${\text{O}}(\log n)$ $\mu$ $\mu \leq {\tfrac {1}{2}}$

Definición [ editar ]

Factor de equilibrio [ editar ]

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

{\text{BF}}(X):={\text{Height}}({\text{RightSubtree}}(X))-{\text{Height}}({\text{LeftSubtree}}(X))

^[6]^{: 459}

de sus dos subárboles secundarios. Un árbol binario se define como un árbol AVL si el invariante

{\text{BF}}(X)\in {\{-1,0,1\}}

^[7]

se mantiene para cada nodo X en el árbol.

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

Propiedades [ editar ]

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 balance de AVL de la forma tradicional, dos bits por nodo son suficientes. Sin embargo, una investigación posterior mostró que si el árbol AVL se implementa como un árbol de rango equilibrado con rangos delta permitidos de 1 o 2, con el significado "cuando se sube hay un incremento adicional en la altura de uno o dos", esto se puede hacer con un poco.

La altura (contada como el número máximo de niveles) de un árbol AVL con nodos se encuentra en el intervalo: ^[6]^:⁴⁶⁰ $h$ $n$

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

donde 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 de la semilla $\varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618$ $b:={\frac {\log _{2}5}{2\log _{2}\varphi }}-2\approx \;-0.3277.$ $h$ $F_{h+2}-1$ $\{F_{n}\}_{n\in \mathbb {N} }$ $F_{1}=F_{2}=1.$

Operaciones [ editar ]

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 binaria no balanceado , pero las modificaciones deben observar y restaurar el equilibrio de altura de los subárboles.

Buscando [ editar ]

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 binaria balanceada o no balanceada . ^[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 requeridas 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}

Recorrido [ editar ]

Como operación de solo lectura, el recorrido de un árbol AVL funciona de la misma manera que en cualquier otro árbol binario. Explorar todos los $n$ nodos del árbol visita cada enlace exactamente dos veces: una visita hacia abajo para ingresar al subárbol enraizado por ese nodo, otra visita hacia arriba para dejar 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 un tiempo constante amortizado . ^[11]^{: 58} Algunas instancias de exploración de estos nodos "cercanos" requieren atravesar hasta $enlaces$ $h \propto log (n)$ (particularmente cuando se navega desde la hoja más a la derecha del subárbol izquierdo de la raíz a la raíz o desde la raíz a 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 siguiente nodo Q a la derecha toma 3 pasos). Dado que hay $n -1$ enlaces en cualquier árbol, el costo amortizado es $2 \times (n -1) / n$ , o aproximadamente 2.

Insertar [ editar ]

Cuando inserta un nodo en un árbol AVL, inicialmente sigue el mismo proceso que para 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. En caso de que el árbol no haya estado vacío, bajamos por la raíz y recursivamente bajamos 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, solo los antepasados del nodo recién insertado están desequilibrados. Esto se debe a que solo esos nodos tienen sus subárboles alterados. ^[12] Por tanto, es necesario comprobar la coherencia de cada uno de los antepasados del nodo con las invariantes de los árboles AVL: esto se denomina "retroceso". 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 comprobado, si el factor de equilibrio temporal permanece en el rango de –1 a +1, solo es necesaria una actualización del factor de equilibrio y no es necesaria una rotación. Sin embargo, si el factor de equilibrio temporal se vuelve menor que -1 o mayor que +1, el subárbol enraizado en este nodo es AVL desequilibrado y se necesita una rotación. ^[9]^{: 52} Con la inserción como muestra el código siguiente, la rotación adecuada reequilibra perfectamente el árbol de inmediato .

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 está en forma AVL.

Código de ejemplo para una operación de inserción

for  ( X  =  parent ( Z );  X  ! =  null ;  X  =  parent ( Z ))  {  // Bucle (posiblemente hasta la raíz) // BF (X) debe actualizarse: if  ( Z  ==  right_child ( X ))  {  // El subárbol derecho aumenta if  ( BF ( X )  >  0 )  {  // X es pesado a la derecha // ==> el temporal BF (X) == +2 // ==> se requiere reequilibrio. G  =  padre ( X );  // Guardar padre de X alrededor de rotaciones if  ( BF ( Z )  <  0 )  // Caso derecho izquierdo (ver figura 3) N  =  rotate_RightLeft ( X ,  Z );  // Doble rotación: Derecha (Z) luego Izquierda (X) else  // Right Right Case (ver figura 2) N  =  rotar_Izquierda ( X ,  Z );  // Rotación única a la izquierda (X) // Después de la rotación, adaptar el enlace principal }  más  { si  ( BF ( X )  <  0 )  { BF ( X )  =  0 ;  // El aumento de altura de Z se absorbe en X. romper ;  // Deja el bucle } BF ( X )  =  + 1 ; Z  =  X ;  // La altura (Z) aumenta en 1 continuar ; } }  else  {  // Z == left_child (X): el subárbol izquierdo aumenta if  ( BF ( X )  <  0 )  {  // X es pesado a la izquierda // ==> el BF (X) temporal == –2 // ==> se requiere reequilibrio. G  =  padre ( X );  // Guardar padre de X alrededor de rotaciones if  ( BF ( Z )  >  0 )  // Izquierda Derecha Caso N  =  rotate_LeftRight ( X ,  Z );  // Doble rotación: Izquierda (Z) luego Derecha (X) else  // Izquierda Izquierda Caso N  =  rotate_Right ( X ,  Z );  // Rotación única a la derecha (X) // Después de la rotación, adaptar el enlace principal }  más  { si  ( BF ( X )  >  0 )  { BF ( X )  =  0 ;  // El aumento de altura de Z se absorbe en X. romper ;  // Deja el bucle } BF ( X )  =  - 1 ; Z  =  X ;  // La altura (Z) aumenta en 1 continuar ; } } // Después de una rotación, adaptar el enlace principal: // N es la nueva raíz del subárbol girado // La altura no cambia: Altura (N) == Altura anterior (X) padre ( N )  =  G ; si  ( G  ! =  nulo )  { si  ( X  ==  hijo_izquierdo ( G )) hijo_izquierdo ( G )  =  N ; demás niño_derecho ( G )  =  N ; }  más árbol -> raíz  =  N ;  // N es la nueva raíz del árbol total romper ; // No hay caídas, solo roturas; o continuar;}// A menos que el bucle se deje a través de la ruptura, la altura del árbol total aumenta en 1.

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 esta ruta, 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 convierte en 0, lo que implica que la altura de ese subárbol permanece sin cambios.

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

Si el factor de equilibrio se convierte temporalmente en ± 2, debe repararse mediante una rotación adecuada, después de lo 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 $O (log n)$ tiempo. ^[9]^{: 53}

Eliminar [ editar ]

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 hijo correspondiente de 1 a 0 o de 2 a 1, si ese nodo tiene un hijo.

A partir de este subárbol, es necesario comprobar la coherencia de cada uno de los antepasados con las invariantes de los árboles AVL. A esto se le llama "retroceder".

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 se convierte en ± 2, entonces el subárbol está desequilibrado y debe rotarse. (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 un significado que el árbol tiene que 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 está en forma AVL.

Código de ejemplo para una operación de eliminación

for  ( X  =  parent ( N );  X  ! =  null ;  X  =  G )  {  // Bucle (posiblemente hasta la raíz) G  =  padre ( X );  // Guardar padre de X alrededor de rotaciones // ¡BF (X) aún no se ha actualizado! if  ( N  ==  left_child ( X ))  {  // el subárbol izquierdo disminuye if  ( BF ( X )  >  0 )  {  // X es pesado a la derecha // ==> el temporal BF (X) == +2 // ==> se requiere reequilibrio. Z  =  niño_derecho ( X );  // Hermano de N (mayor en 2) b  =  BF ( Z ); if  ( b  <  0 )  // Caso derecho izquierdo (ver figura 3) N  =  rotate_RightLeft ( X ,  Z );  // Doble rotación: Derecha (Z) luego Izquierda (X) else  // Right Right Case (ver figura 2) N  =  rotar_Izquierda ( X ,  Z );  // Rotación única a la izquierda (X) // Después de la rotación, adaptar el enlace principal }  más  { si  ( BF ( X )  ==  0 )  { BF ( X )  =  + 1 ;  // La disminución de la altura de N se absorbe en X. romper ;  // Deja el bucle } N  =  X ; BF ( N )  =  0 ;  // La altura (N) disminuye en 1 continuar ; } }  else  {  // (N == right_child (X)): El subárbol derecho disminuye if  ( BF ( X )  <  0 )  {  // X es pesado a la izquierda // ==> el BF (X) temporal == –2 // ==> se requiere reequilibrio. Z  =  hijo_izquierdo ( X );  // Hermano de N (mayor en 2) b  =  BF ( Z ); if  ( b  >  0 )  // Izquierda Derecha Caso N  =  rotate_LeftRight ( X ,  Z );  // Doble rotación: Izquierda (Z) luego Derecha (X) else  // Izquierda Izquierda Caso N  =  rotate_Right ( X ,  Z );  // Rotación única a la derecha (X) // Después de la rotación, adaptar el enlace principal }  más  { si  ( BF ( X )  ==  0 )  { BF ( X )  =  - 1 ;  // La disminución de la altura de N se absorbe en X. romper ;  // Deja el bucle } N  =  X ; BF ( N )  =  0 ;  // La altura (N) disminuye en 1 continuar ; } } // Después de una rotación, adaptar el enlace principal: // N es la nueva raíz del subárbol girado padre ( N )  =  G ; si  ( G  ! =  nulo )  { si  ( X  ==  hijo_izquierdo ( G )) hijo_izquierdo ( G )  =  N ; demás niño_derecho ( G )  =  N ; }  más árbol -> raíz  =  N ;  // N es la nueva raíz del árbol total  si  ( b  ==  0 ) romper ;  // La altura no cambia: deja el bucle  // La altura (N) disminuye en 1 (== altura anterior (X) –1)}// Si (b! = 0) la altura del árbol total disminuye en 1.

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, debe repararse mediante una rotación adecuada. Depende del factor de equilibrio del hermano Z (el árbol hijo más alto 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 [ editar ]

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 árboles AVL: unión , intersección y diferencia de conjuntos . Luego, se pueden implementar operaciones masivas rápidas en inserciones o eliminaciones basadas en estas funciones establecidas. Estas operaciones de conjunto se basan en dos operaciones auxiliares, Split y Join . 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 1$ y $t 2$ y una tecla $k$ devolverá un árbol que contiene todos los elementos en $t 1$ , $t 2$ así como $k$ . Requiere que $k$ sea mayor que todas las claves en $t 1$ y menor que todas las claves en $t 2$ . Si los dos árboles difieren en altura como máximo uno, Join simplemente crea un nuevo nodo con el subárbol izquierdo $t 1$ , raíz $k$ y el subárbol derecho $t 2$ . De lo contrario, suponga que $t 1$ es mayor que $t 2$ para más de uno (el otro caso es simétrico). La unión sigue la espina dorsal derecha de $t 1$ hasta un nodo $c$ que está equilibrado con $t 2$ . En este punto,se creaun nuevo nodo con el hijo izquierdo $c$ , la raíz $k$ y el hijo derecho $t 2$ para reemplazar c. El nuevo nodo satisface el invariante AVL, y su altura es mayor que $c$ . El aumento de altura puede aumentar la altura de sus antepasados, posiblemente invalidando la invariante AVL de esos nodos. Esto se puede solucionar con una doble rotación si no es válido en el padre o con una sola rotación a la izquierda si no es válido más arriba en el árbol, en ambos casos restaurando la altura para cualquier otro nodo ancestro. Únete por lo tanto, será necesario en la mayoría de dos rotaciones. El costo de esta función es la diferencia de alturas entre los dos árboles de entrada.

Implementación de pseudocódigo para el algoritmo Join

función JoinRightAVL (T _L , k, T _R ) (l, k ', c) = exponer (T _L ) si (Altura (c) <= Altura (T _R ) +1) T '= Nodo (c, k, T _R ) si (Altura (T ') <= Altura (l) +1) entonces devuelve Nodo (l, k', T ') else return rotateLeft (Node (l, k'rotateRight (T '))) else T' = JoinRightAVL (c, k, T _R ) T = Nodo (l, k ', T')  si (Altura (T ') <= Altura (l) +1) devuelve T de lo contrario  volver rotateLeft (T )

función JoinLeftAVL (T _L , k, T _R ) / * simétrico a JoinRightAVL * /

función Unir (T _L , k, T _R ) si (Altura (T _L )> Altura (T _R ) +1) return Unir DerechaAVL (T _L , k, T _R ) if (Altura (T _R )> Altura (T _L ) +1) return JoinLeftAVL (T _L , k, T _R ) return Node (T _L , k, T _R )

Aquí la altura (v) es la altura de un subárbol (nodo) $v$ . (l, k, r) = ficha (v) los extractos $v$ 's izquierda niño $l$ , la clave $k$ de $v$ ' root s, y el hijo derecho $r$ . Nodo (l, k, r) significa crear un nodo del hijo izquierdo $l$ , la tecla $k$ y el hijo derecho $r$ .

Para dividir un árbol AVL en dos árboles más pequeños, los más pequeños que la clave $k$ y los más grandes 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.

Implementación de pseudocódigo para el algoritmo Split

función Split (T, k) if (T = nil) return (nil, false, nil) (L, m, R) = exponer (T) si (k = m) devuelve (L, verdadero, R) si (k <m) (L ', b, R') = dividir (L, k) return (L ', b, join (R', m, R)) si (k> m) (L ', b, R') = dividir (R, k) volver (unirse (L, m, L '), b, R'))

La unión de dos árboles AVL $t 1$ y $t 2$ conjuntos que representan $A$ y $B$ , es un AVL $t$ que representa $A \cup B$ .

Implementación de pseudocódigo para el algoritmo Union

función Unión (t ₁ , t ₂ ): si t ₁ = nulo: devuelve t ₂ si t ₂ = nulo: devuelve t ₁ t _< , t _> ← dividir t ₂ en t ₁ .root volver a unir (t ₁ .root, unión (izquierda (t ₁ ), t _< ), unión (derecha (t ₁ ), t _> ))

Aquí, se supone que Split devuelve dos árboles: uno que sostiene las teclas menos su tecla de entrada, otro que sostiene las teclas mayores. (El algoritmo no es destructivo , pero también existe una versión destructiva in situ).

El algoritmo de intersección o diferencia es similar, pero requiere la rutina auxiliar Join2 que es la misma que Join pero sin la tecla del medio. Según las nuevas funciones de unión, intersección o diferencia, se puede insertar o eliminar una o varias teclas del árbol AVL. Dado que Split llama a Join pero no se ocupa de los criterios de equilibrio de los árboles AVL directamente, esta implementación se suele denominar implementación "basada en uniones" .

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 uniones tiene el mismo DAG computacional que la inserción y eliminación de un solo elemento. ${\text{O}}\left(m\log \left({n \over m}+1\right)\right)$ $m$ $n\;(\geq m)$ ${\text{O}}(\log m\log n)$ $m=1$

Reequilibrio [ editar ]

Si durante una operación de modificación cambia la diferencia de altura entre dos subárboles secundarios, esto puede, siempre que sea <2, reflejarse en 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 ser "reequilibrado". Las herramientas de reparación dadas son las llamadas rotaciones de árbol , porque mueven las teclas solo "verticalmente", de modo que la secuencia ("horizontal") en orden de las teclas se conserva completamente (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 superior (véanse las figuras 2 y 3). Tenga en cuenta que ambos niños están en forma AVL por hipótesis de inducción .

En caso de inserción, esta inserción le ha ocurrido 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 sucedido al hermano t ₁ de Z de tal manera que la altura de t ₁ , que ya es más baja, ha disminuido. (Este 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:

Bien bien	==> Z es un derecho	hijo de su padre X y BF (Z) ≥ 0
Izquierda izquierda	==> Z es una izquierda	hijo de su padre X y BF (Z) ≤ 0
Derecha izquierda	==> Z es un derecho	hijo de su padre X y BF (Z) <0
Izquierda derecha	==> Z es una izquierda	hijo de su padre X y BF (Z)> 0

Y el reequilibrio se realiza de forma diferente:

Bien bien	==> X se reequilibra con un	sencillo	rotación `rotate_Left`	(ver figura 2)
Izquierda izquierda	==> X se reequilibra con un	sencillo	rotación `rotate_Right`	(imagen especular de la figura 2)
Derecha izquierda	==> X se reequilibra con un	doble	rotación `rotate_RightLeft`	(ver figura 3)
Izquierda derecha	==> X se reequilibra con un	doble	rotación `rotate_LeftRight`	(imagen especular de la figura 3)

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

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

Rotación simple [ editar ]

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 niño interior t ₂₃ de Z (es decir, el niño izquierdo cuando Z es el niño derecho o el niño derecho cuando Z es el niño 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 producirse la situación pálida en la que 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 actualizarán 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 deleción, la capa de hojas se encontraba en el nivel h + 2, donde se encuentra nuevamente, cuando t ₂₃ y t ₄ eran de la misma altura. De lo contrario, la capa de hojas alcanza el nivel h + 1, por lo que la altura del árbol girado disminuye.

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

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

Aporte:	X = raíz del subárbol que se rotará a la izquierda
	Z = hijo derecho de X, Z es pesado a la derecha
	con altura == $Altura (LeftSubtree ($ X $)) + 2$
Resultado:	nueva raíz del subárbol reequilibrado

nodo  * rotate_Left ( nodo  * X ,  nodo  * Z )  { // Z es 2 más alto que su hermano t23  =  hijo_izquierdo ( Z );  // Hijo 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, // solo ocurre con la eliminación, no con la inserción: if  ( BF ( Z )  ==  0 )  {  // t23 ha sido de la misma altura que t4 BF ( X )  =  + 1 ;  // t23 ahora más alto BF ( Z )  =  - 1 ;  // t4 ahora menor que X }  más {  // El segundo caso ocurre con la inserción o eliminación: BF ( X )  =  0 ; BF ( Z )  =  0 ; } return  Z ;  // devuelve la nueva raíz del subárbol girado}

Doble rotación [ editar ]

La Figura 3 muestra una situación 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 más alto que su hermano t ₄ . Esto puede suceder por la inserción de la propia 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 ₁ . En el último caso, también puede ocurrir que t ₂ y t ₃ sean de 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 AVL, porque la diferencia de altura entre Y y t ₄ es solo 1.) El resultado de la rotación final a 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 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 deleció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 girado 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 de derecha a izquierda

Aporte:	X = raíz del subárbol a rotar
	Z = su hijo derecho, izquierdo pesado
	con altura == $Altura (LeftSubtree ($ X $)) + 2$
Resultado:	nueva raíz del subárbol reequilibrado

nodo  * rotate_RightLeft ( nodo  * X ,  nodo  * Z )  { // Z es 2 más alto que su hermano Y  =  hijo_izquierdo ( Z );  // Hijo interior de Z // Y es en 1 mayor que el hermano t3  =  niño_derecho ( Y ); hijo_izquierdo ( Z )  =  t3 ; si  ( t3  ! =  nulo ) padre ( t3 )  =  Z ; hijo_derecho ( Y )  =  Z ; padre ( Z )  =  Y ; t2  =  hijo_izquierdo ( Y ); hijo_derecho ( X )  =  t2 ; si  ( t2  ! =  nulo ) padre ( t2 )  =  X ; hijo_izquierdo ( Y )  =  X ; padre ( X )  =  Y ; // 1er caso, BF (Y) == 0, // solo ocurre con la eliminación, no con la inserción: si  ( BF ( Y )  ==  0 )  { BF ( X )  =  0 ; BF ( Z )  =  0 ; }  más // otros casos ocurren con inserción o eliminación: if  ( BF ( Y )  >  0 )  {  // t3 fue mayor BF ( X )  =  - 1 ;  // t1 ahora más alto BF ( Z )  =  0 ; }  más  { // t2 fue mayor BF ( X )  =  0 ; BF ( Z )  =  + 1 ;  // t4 ahora más alto } BF ( Y )  =  0 ; return  Y ;  // devuelve la nueva raíz del subárbol girado}

Comparación con otras estructuras [ editar ]

Tanto los árboles AVL como los árboles rojo-negro (RB) son árboles de búsqueda binaria autoequilibrados y están relacionados matemáticamente. De hecho, todos los árboles AVL pueden ser de color rojo-negro, ^[14] pero hay árboles RB que no tienen AVL equilibrados. Para mantener el AVL resp. Los invariantes del árbol 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 resp. Colores RB. Las inserciones y deleciones de RB y las inserciones de AVL requieren de cero a tres rotaciones recursivas de la cola y se ejecutan en un tiempo $O (1)$ amortizado , ^[15]^{[16] por lo} tanto igualmente constante en promedio. Deleciones AVL que requieren $Las$ 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 con un significado «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 \geq 1$

la altura de un árbol AVL es como máximo
${\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 .

\varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618

c:={\tfrac {1}{\log _{2}\varphi }}\approx 1.440,

b:={\tfrac {c}{2}}\log _{2}5-2\approx \;-0.328,

d:=1+{\tfrac {1}{\varphi ^{4}{\sqrt {5}}}}\approx 1.065

la altura de un árbol RB es como máximo
${\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 mediana ≈0,947 y media geométrica ≈0,910. ^[4]

Ver también [ editar ]

Árboles
Rotación de árboles
Árbol WAVL
Árbol rojo-negro
Árbol de esparcimiento
Árbol de chivo expiatorio
Árbol B
Árbol T
Lista de estructuras de datos

Referencias [ editar ]

^ a b c d e f Eric Alexander. "Árboles AVL" . Archivado desde el original el 31 de julio de 2019.CS1 maint: unfit URL (link)
^ Sedgewick, Robert (1983). "Balanced Trees". Algorithms. Addison-Wesley. p. 199. ISBN 0-201-06672-6.
^ Adelson-Velsky, Georgy; Landis, Evgenii (1962). "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences (in Russian). 146: 263–266. English translation by Myron J. Ricci in Soviet Mathematics - Doklady, 3:1259–1263, 1962.
^ a b Pfaff, Ben (June 2004). "Performance Analysis of BSTs in System Software" (PDF). Stanford University.
^ AVL trees are not weight-balanced? (meaning: AVL trees are not μ-balanced?)
Thereby: A Binary Tree is called $\mu$ -balanced, with $0\leq \mu \leq {\tfrac {1}{2}}$ , if for every node $N$ , the inequality
${\tfrac {1}{2}}-\mu \leq {\tfrac {|N_{l}|}{|N|+1}}\leq {\tfrac {1}{2}}+\mu$
holds and $\mu$ is minimal with this property. $|N|$ is the number of nodes below the tree with $N$ as root (including the root) and $N_{l}$ is the left child node of $N$ .
^ a b c d Knuth, Donald E. (2000). Sorting and searching (2. ed., 6. printing, newly updated and rev. ed.). Boston [u.a.]: Addison-Wesley. ISBN 0-201-89685-0.
^ Rajinikanth. "AVL Tree : Data Structures". btechsmartclass.com. Retrieved 2018-03-09.
^ Dixit, J. B. (2010). Mastering data structures through 'C' language. New Delhi, India: University Science Press, an imprint of Laxmi Publications Pvt. Ltd. ISBN 9789380386720. OCLC 939446542.
^ a b c Brass, Peter (2008). Advanced data structures. Cambridge: Cambridge University Press. ISBN 9780511438202. OCLC 312435417.
^ Hubbard, John Rast (2000). Schaum's outline of theory and problems of data structures with Java. New York: McGraw-Hill. ISBN 0071378707. OCLC 48139308.
^ a b c Pfaff, Ben (2004). An Introduction to Binary Search Trees and Balanced Trees. Free Software Foundation, Inc.
^ Weiss, Mark Allen. (2006). Data structures and algorithm analysis in C++ (3rd ed.). Boston: Pearson Addison-Wesley. p. 145. ISBN 0-321-37531-9. OCLC 61278554.CS1 maint: date and year (link)
^ a b Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just join for parallel ordered sets", Symposium on Parallel Algorithms and Architectures, ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID 2897793.
^ Paul E. Black (2015-04-13). "AVL tree". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved 2016-07-02.
^ Mehlhorn & Sanders 2008, pp. 165, 158
^ Dinesh P. Mehta, Sartaj Sahni (Ed.) Handbook of Data Structures and Applications 10.4.2
^ Red–black tree#Proof of asymptotic bounds

External links[edit]

The Wikibook Algorithm Implementation has a page on the topic of: AVL tree

Wikimedia Commons has media related to AVL-trees.

This article incorporates public domain material from the NIST document: Black, Paul E. "AVL Tree". Dictionary of Algorithms and Data Structures.

[wiscurl-1] Eric Alexander. "Árboles AVL" . Archivado desde el original el 31 de julio de 2019.CS1 maint: unfit URL (link)

[2] Sedgewick, Robert (1983). "Balanced Trees". Algorithms. Addison-Wesley. p. 199. ISBN 0-201-06672-6.

[3] Adelson-Velsky, Georgy; Landis, Evgenii (1962). "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences (in Russian). 146: 263–266. English translation by Myron J. Ricci in Soviet Mathematics - Doklady, 3:1259–1263, 1962.

[Pfaff1-4] Pfaff, Ben (June 2004). "Performance Analysis of BSTs in System Software" (PDF). Stanford University.

[5] AVL trees are not weight-balanced? (meaning: AVL trees are not μ-balanced?)
Thereby: A Binary Tree is called $\mu$ -balanced, with $0\leq \mu \leq {\tfrac {1}{2}}$ , if for every node $N$ , the inequality
${\tfrac {1}{2}}-\mu \leq {\tfrac {|N_{l}|}{|N|+1}}\leq {\tfrac {1}{2}}+\mu$
holds and $\mu$ is minimal with this property. $|N|$ is the number of nodes below the tree with $N$ as root (including the root) and $N_{l}$ is the left child node of $N$ .

[Knuth-6] Knuth, Donald E. (2000). Sorting and searching (2. ed., 6. printing, newly updated and rev. ed.). Boston [u.a.]: Addison-Wesley. ISBN 0-201-89685-0.

[7] Rajinikanth. "AVL Tree : Data Structures". btechsmartclass.com. Retrieved 2018-03-09.

[dixit-mastering-data-structures-8] Dixit, J. B. (2010). Mastering data structures through 'C' language. New Delhi, India: University Science Press, an imprint of Laxmi Publications Pvt. Ltd. ISBN 9789380386720. OCLC 939446542.

[brass-advanced-data-structures-9] Brass, Peter (2008). Advanced data structures. Cambridge: Cambridge University Press. ISBN 9780511438202. OCLC 312435417.

[hubbard-outline-theory-problems-10] Hubbard, John Rast (2000). Schaum's outline of theory and problems of data structures with Java. New York: McGraw-Hill. ISBN 0071378707. OCLC 48139308.

[Pfaff-11] Pfaff, Ben (2004). An Introduction to Binary Search Trees and Balanced Trees. Free Software Foundation, Inc.

[12] Weiss, Mark Allen. (2006). Data structures and algorithm analysis in C++ (3rd ed.). Boston: Pearson Addison-Wesley. p. 145. ISBN 0-321-37531-9. OCLC 61278554.CS1 maint: date and year (link)

[join-based-13] Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just join for parallel ordered sets", Symposium on Parallel Algorithms and Architectures, ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID 2897793.

[14] Paul E. Black (2015-04-13). "AVL tree". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved 2016-07-02.

[15] Mehlhorn & Sanders 2008, pp. 165, 158

[Dinesh-16] Dinesh P. Mehta, Sartaj Sahni (Ed.) Handbook of Data Structures and Applications 10.4.2

[17] Red–black tree#Proof of asymptotic bounds

[1]

vteTree data structures
Search trees(dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* Bx (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal Fibonacci Leftist Pairing Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

vteData structures
Types	Collection Container
Abstract	Associative array Multimap List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures