Árbol AVL

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 23 de octubre de 2021; las comprobaciones requieren 6 ediciones .
árbol AVL
inglés  árbol AVL
Tipo de árbol de búsqueda
año de invención 1968
Autor Adelson-Velsky Georgy Maksimovich y Landis Evgeny Mikhailovich
Complejidad en los símbolos O
Promedio Lo peor
Consumo de memoria En) En)
Búsqueda O (registro n) O (registro n)
Insertar O (registro n) O (registro n)
Eliminación O (registro n) O (registro n)
 Archivos multimedia en Wikimedia Commons

Un árbol AVL es un árbol de búsqueda binaria  de altura equilibrada : para cada uno de sus vértices, la altura de sus dos subárboles difiere en no más de 1.

AVL es una abreviatura formada por las primeras letras de los creadores (científicos soviéticos) Adelson-Velsky Georgy Maksimovich y Landis Evgeny Mikhailovich .

Altura máxima

La altura máxima de un árbol AVL para un número determinado de nodos [1] :

dónde:

(redondeo)

(redondear a la baja)

(redondear a la baja).

El número de alturas posibles es muy limitado en la práctica (con direccionamiento de 32 bits la altura máxima es 45, con direccionamiento de 48 bits es 68), por lo que probablemente sea mejor precalcular todos los valores del número mínimo de nodos para cada altura utilizando la fórmula recursiva del árbol de Fibonacci :

,

,

.

Los valores intermedios del número de nodos corresponderán a la altura anterior (inferior).

Equilibrio

Con respecto a un árbol AVL, el equilibrio de vértices es una operación que, si la diferencia de altura de los subárboles izquierdo y derecho = 2, cambia los enlaces padre-hijo en el subárbol de este vértice para que la diferencia sea <= 1, de lo contrario no cambia nada. El resultado indicado se obtiene por rotaciones del subárbol del vértice dado.

Se utilizan 4 tipos de rotaciones:

1. Pequeña rotación a la izquierda Esta rotación se usa cuando la diferencia de altura entre el subárbol a y el subárbol b es 2 y la altura C <= altura R.

2. Gran rotación a la izquierda Esta rotación se utiliza cuando la diferencia de altura entre el subárbol a y el subárbol b es 2 y la altura del subárbol c > altura R.

3. Pequeña rotación a la derecha Esta rotación se usa cuando la diferencia de altura entre el subárbol a y el subárbol b es 2 y la altura C <= altura L.

4. Gran rotación a la derecha Esta rotación se utiliza cuando la diferencia de altura entre el subárbol a y el subárbol b es 2 y la altura del subárbol c > altura L.

En cada caso, es suficiente probar simplemente que la operación conduce al resultado deseado y que la altura total disminuye como máximo en 1 y no puede aumentar. También un giro grande es una combinación de giro pequeño a la derecha y a la izquierda. Debido a la condición de equilibrio, la altura del árbol es O(log(N)), donde N es el número de vértices, por lo que agregar un elemento requiere operaciones O(log(N)).

Algoritmo para agregar un vértice

El indicador de equilibrio se interpretará además como la diferencia entre la altura de los subárboles izquierdo y derecho, y el algoritmo se basará en el tipo TAVLTree descrito anteriormente. Directamente al momento de la inserción (hoja) se le asigna un saldo cero. El proceso de incluir un vértice consta de tres partes (este proceso lo describe Niklaus Wirth en Algorithms and Data Structures):

  1. Pase por la ruta de búsqueda hasta que estemos seguros de que la clave no está en el árbol.
  2. Incluir un nuevo vértice en el árbol y determinar los indicadores de equilibrio resultantes.
  3. "Retrocesos" por el camino de búsqueda y verificación en cada vértice del indicador de saldo. Si es necesario, equilibre.

Devolveremos como resultado de la función si la altura del árbol ha disminuido o no. Suponga que un proceso de la rama izquierda regresa al padre (la recursividad regresa), entonces son posibles tres casos: { h l  - altura del subárbol izquierdo, h r  - altura del subárbol derecho } Incluyendo un vértice en el subárbol izquierdo resultará en

  1. h l < h r : iguala h l = h r . No hay que hacer nada.
  2. h l = h r : ahora el subárbol izquierdo será uno más grande, pero aún no es necesario equilibrar.
  3. h l > h r : ahora h l  - h r = 2, - se requiere equilibrio.

En la tercera situación, se requiere determinar el equilibrio del subárbol izquierdo. Si el subárbol izquierdo de este vértice (Árbol^.izquierda^.izquierda) es más alto que el de la derecha (Árbol^.izquierda^.derecha), entonces se requiere una gran rotación a la derecha, de lo contrario, una pequeña a la derecha será suficiente. Se puede dar un razonamiento similar (simétrico) para incluirlo en el subárbol derecho.

Algoritmo para borrar un vértice

Para simplificar, describimos un algoritmo de eliminación recursivo. Si el vértice es una hoja, lo eliminamos y llamamos al equilibrio de todos sus ancestros en orden desde el padre hasta la raíz. De lo contrario, buscamos el vértice más cercano en valor en el subárbol de mayor altura (derecha o izquierda) y lo movemos al lugar del vértice a eliminar, mientras llamamos al procedimiento de eliminación.

Probemos que este algoritmo preserva el equilibrio. Para ello demostramos por inducción sobre la altura del árbol que después de quitar algún vértice del árbol y posterior balanceo, la altura del árbol disminuye en no más de 1. Base de la inducción: Para una hoja, evidentemente cierto. Paso de inducción: no se viola la condición de equilibrio en la raíz (después de la eliminación, la raíz puede cambiar), entonces la altura del árbol dado no ha cambiado, o el subárbol estrictamente más pequeño ha disminuido => la altura antes del equilibrio ha no cambiado => después de eso, disminuirá en no más de 1.

Obviamente, como resultado de estas acciones, el procedimiento de eliminación no se llama más de 3 veces, ya que el vértice eliminado por la segunda llamada no tiene uno de los subárboles. Pero encontrar el más cercano requiere operaciones O(N) cada vez. La posibilidad de optimización se vuelve obvia: la búsqueda del vértice más cercano se puede realizar a lo largo del borde del subárbol, lo que reduce la complejidad a O(log(N)).

Inserción de arriba hacia abajo no recursiva en un árbol AVL

Un algoritmo no recursivo es más complicado que uno recursivo.

  1. Se encuentran el punto de inserción y el vértice, cuya altura no cambiará durante la inserción (este es el vértice para el cual la altura del subárbol izquierdo no es igual a la altura del derecho; lo llamaremos PrimeNode)
  2. El descenso desde PrimeNode hasta el punto de inserción se realiza con un cambio de saldos
  3. PrimeNode se reequilibra cuando hay un desbordamiento

Eliminación no recursiva de arriba a abajo de un árbol AVL

Para implementar la eliminación, procederemos del mismo principio que al insertar: encontraremos un vértice, cuya eliminación no conducirá a un cambio en su altura. Hay dos casos:

  1. la altura del subárbol izquierdo es igual a la altura del subárbol derecho (excepto cuando la hoja no tiene subárboles)
  2. la altura del árbol en la dirección del movimiento es menor que el opuesto ("hermano" de la dirección) y el balance del "hermano" es 0 (analizar esta opción es bastante complicado, por lo que aún no hay pruebas)

Para facilitar la comprensión, el algoritmo anterior no contiene ninguna optimización. A diferencia del algoritmo recursivo, el vértice eliminado encontrado se reemplaza por el valor de la subrama izquierda. Este algoritmo se puede optimizar de la misma manera que el recursivo (debido a que después de encontrar el vértice a eliminar, se conoce la dirección del movimiento):

  1. buscamos el elemento a borrar y por el camino encontramos nuestro maravilloso top
  2. hacemos cambios de saldos, si es necesario, hacemos rebalanceos
  3. elimine nuestro elemento (en realidad no lo eliminamos, sino que reemplazamos su clave y valor, dar cuenta de las permutaciones de los vértices será un poco más complicado)

Disposición de saldos a la baja

Como ya se mencionó, si el vértice a eliminar es una hoja, entonces se elimina y el recorrido inverso del árbol ocurre desde el padre de la hoja eliminada. Si no es una hoja, se encuentra un "reemplazo" para ella, y el recorrido inverso del árbol proviene del padre "reemplazo". Inmediatamente después de la eliminación del elemento, el "reemplazo" recibe el saldo del nodo eliminado.

En el bypass inverso: si durante la transición al padre venían por la izquierda, el saldo aumenta en 1, si venían por la derecha, disminuye en 1.

Esto se hace hasta que el balance cambia a -1 o 1 (¡observe la diferencia al insertar un elemento!): en este caso, tal cambio de balance indicaría una altura delta constante de los subárboles. Las rotaciones siguen las mismas reglas que al insertar.

Disposición de saldos a un solo turno

Denotar:

Si la rotación ocurre cuando se inserta un elemento, entonces el balance de Pivot es 1 o −1. En este caso, después de la rotación, los saldos de ambos se igualan a 0. Al borrar, todo es diferente: el saldo de Pivot puede volverse igual a 0 (esto es fácil de verificar).

Aquí hay una tabla resumen de la dependencia de los balances finales en la dirección de rotación y el balance inicial del nodo Pivot:

dirección de giro Equilibrio de pivote antiguo Nuevo saldo actual Nuevo equilibrio de pivote
Izquierda o derecha -1 o +1 0 0
Derecha 0 -una +1
Izquierda 0 +1 -una

Balanzas de doble vuelta

Pivot y Current son lo mismo, pero se agrega un tercer miembro del giro. Designémoslo como "Abajo": es (con un doble giro a la derecha) el hijo izquierdo de Pivot, y con un doble giro a la izquierda, el hijo derecho de Pivot.

Con esta rotación, Bottom siempre adquiere como resultado un saldo de 0, pero la disposición de saldos para Pivot y Current depende de su saldo inicial.

Aquí hay una tabla resumen de la dependencia de los saldos finales en la dirección de rotación y el saldo inicial del Nodo inferior:

Dirección Saldo inferior antiguo Nuevo saldo actual Nuevo equilibrio de pivote
Izquierda o derecha 0 0 0
Derecha +1 0 -una
Derecha -una +1 0
Izquierda +1 -una 0
Izquierda -una 0 +1

Evaluación del desempeño

De la fórmula anterior, la altura de un árbol AVL nunca excederá la altura de un árbol perfectamente equilibrado en más del 45 %. Para grandes , tenemos la estimación . Por lo tanto, realizar operaciones básicas requiere un orden de comparaciones. Se ha encontrado experimentalmente que ocurre un equilibrio por cada 2 inclusiones y por cada 5 excepciones.

Véase también

Árboles equilibrados (autoequilibrados):

Notas

  1. ↑ D. Knut. Arte de Programar. Ordenar y buscar. - S. 460.

Literatura