El árbol AVL fue inventado por GM Adelson - Velsky y EM Landis en 1962. El árbol lleva el nombre AVL en honor a sus inventores.
El árbol AVL se puede definir como un árbol de búsqueda binario con altura equilibrada en el que cada nodo está asociado con un factor de equilibrio que se calcula restando la altura de su subárbol derecho de la de su subárbol izquierdo.
Se dice que el árbol está equilibrado si el factor de equilibrio de cada nodo está entre -1 y 1; de lo contrario, el árbol estará desequilibrado y será necesario equilibrarlo.
Factor de equilibrio (k) = altura (izquierda(k)) - altura (derecha(k))
Si el factor de equilibrio de cualquier nodo es 1, significa que el subárbol izquierdo está un nivel más alto que el subárbol derecho.
Si el factor de equilibrio de cualquier nodo es 0, significa que el subárbol izquierdo y el subárbol derecho tienen la misma altura.
Si el factor de equilibrio de cualquier nodo es -1, significa que el subárbol izquierdo está un nivel más bajo que el subárbol derecho.
En la siguiente figura se muestra un árbol AVL. Podemos ver que el factor de equilibrio asociado a cada nodo está entre -1 y +1. por tanto, es un ejemplo de árbol AVL.
Complejidad
| Algoritmo | Caso promedio | Peor de los casos |
|---|---|---|
| Espacio | en) | en) |
| Buscar | o(log n) | o(log n) |
| Insertar | o(log n) | o(log n) |
| Borrar | o(log n) | o(log n) |
Operaciones en el árbol AVL
Debido a que el árbol AVL también es un árbol de búsqueda binario, todas las operaciones se realizan de la misma manera que se realizan en un árbol de búsqueda binario. La búsqueda y el recorrido no conducen a la violación de la propiedad del árbol AVL. Sin embargo, la inserción y la eliminación son operaciones que pueden violar esta propiedad y, por lo tanto, es necesario revisarlas.
| SN | Operación | Descripción |
|---|---|---|
| 1 | Inserción | La inserción en el árbol AVL se realiza de la misma manera que en un árbol de búsqueda binario. Sin embargo, puede provocar una violación de la propiedad del árbol AVL y, por lo tanto, es posible que sea necesario equilibrar el árbol. El árbol se puede equilibrar aplicando rotaciones. |
| 2 | Supresión | La eliminación también se puede realizar de la misma manera que se realiza en un árbol de búsqueda binario. La eliminación también puede alterar el equilibrio del árbol, por lo que se utilizan varios tipos de rotaciones para reequilibrar el árbol. |
¿Por qué árbol AVL?
El árbol AVL controla la altura del árbol de búsqueda binaria al no permitir que se sesgue. El tiempo necesario para todas las operaciones en un árbol de búsqueda binario de altura h es Oh) . Sin embargo, puede extenderse a En) si el BST se desvía (es decir, en el peor de los casos). Al limitar esta altura a log n, el árbol AVL impone un límite superior en cada operación que se realizará. O(log n) donde n es el número de nodos.
Rotaciones AVL
Realizamos rotación en el árbol AVL solo en caso de que el Factor de equilibrio sea distinto de -1, 0 y 1 . Básicamente existen cuatro tipos de rotaciones que son las siguientes:
- Rotación L L: el nodo insertado está en el subárbol izquierdo del subárbol izquierdo de A
- Rotación R R: el nodo insertado está en el subárbol derecho del subárbol derecho de A
- Rotación L R: el nodo insertado está en el subárbol derecho del subárbol izquierdo de A
- Rotación R L: el nodo insertado está en el subárbol izquierdo del subárbol derecho de A
Donde el nodo A es el nodo cuyo factor de equilibrio es distinto de -1, 0, 1.
Las dos primeras rotaciones LL y RR son rotaciones simples y las dos siguientes rotaciones LR y RL son rotaciones dobles. Para que un árbol esté desequilibrado, la altura mínima debe ser al menos 2. Entendamos cada rotación.
1. Rotación RR
Cuando BST se desequilibra, debido a que un nodo se inserta en el subárbol derecho del subárbol derecho de A, entonces realizamos la rotación RR, la rotación RR es una rotación en sentido antihorario, que se aplica en el borde debajo de un nodo que tiene un factor de equilibrio -2
En el ejemplo anterior, el nodo A tiene un factor de equilibrio -2 porque se inserta un nodo C en el subárbol derecho del subárbol derecho A. Realizamos la rotación RR en el borde debajo de A.
ordenar lista de matrices
2. Rotación LL
Cuando BST se desequilibra, debido a que un nodo se inserta en el subárbol izquierdo del subárbol izquierdo de C, entonces realizamos la rotación LL, la rotación LL es una rotación en el sentido de las agujas del reloj, que se aplica en el borde debajo de un nodo que tiene un factor de equilibrio 2.
En el ejemplo anterior, el nodo C tiene un factor de equilibrio 2 porque se inserta un nodo A en el subárbol izquierdo del subárbol izquierdo C. Realizamos la rotación LL en el borde debajo de A.
3. Rotación LR
Las rotaciones dobles son un poco más difíciles que las rotaciones simples, como ya se explicó anteriormente. Rotación LR = rotación RR + rotación LL, es decir, la primera rotación RR se realiza en el subárbol y luego la rotación LL se realiza en el árbol completo; por árbol completo nos referimos al primer nodo de la ruta del nodo insertado cuyo factor de equilibrio es distinto de -1 , 0 o 1.
Entendamos muy claramente todos y cada uno de los pasos:
| Estado | Acción |
|---|---|
 | Un nodo B se ha insertado en el subárbol derecho de A, el subárbol izquierdo de C, por lo que C se ha convertido en un nodo desequilibrado que tiene un factor de equilibrio 2. Este caso es la rotación L R donde: El nodo insertado está en el subárbol derecho del subárbol izquierdo de C |
 | Como rotación LR = rotación RR + LL, por lo tanto, primero se realiza RR (en sentido antihorario) en el subárbol con raíz en A. Al hacer rotación RR, el nodo A , se ha convertido en el subárbol izquierdo de B . |
 | Después de realizar la rotación RR, el nodo C todavía está desequilibrado, es decir, tiene un factor de equilibrio 2, ya que el nodo A insertado está a la izquierda de la izquierda de C |
 | Ahora realizamos la rotación LL en el sentido de las agujas del reloj en el árbol completo, es decir, en el nodo C. C ahora se ha convertido en el subárbol derecho del nodo B, A es el subárbol izquierdo de B |
 | El factor de equilibrio de cada nodo ahora es -1, 0 o 1, es decir, BST ahora está equilibrado. |
4. Rotación RL
Como ya se mencionó, las rotaciones dobles son un poco más difíciles que las rotaciones simples, como ya se explicó anteriormente. Rotación R L = rotación LL + rotación RR, es decir, la primera rotación LL se realiza en el subárbol y luego la rotación RR se realiza en el árbol completo; por árbol completo nos referimos al primer nodo de la ruta del nodo insertado cuyo factor de equilibrio es distinto de -1 , 0 o 1.
| Estado | Acción |
|---|---|
 | un nodo B se ha insertado en el subárbol izquierdo de C el subárbol derecho de A , debido a que A se ha convertido en un nodo desequilibrado con un factor de equilibrio - 2. Este caso es una rotación RL donde: El nodo insertado está en el subárbol izquierdo del subárbol derecho de A. |
 | Como rotación RL = rotación LL + rotación RR, por lo tanto, LL (en el sentido de las agujas del reloj) en el subárbol con raíz en C se realiza primero. Al hacer rotación RR, el nodo C se ha convertido en el subárbol derecho de B . |
 | Después de realizar la rotación LL, el nodo A todavía está desequilibrado, es decir, tiene un factor de equilibrio -2, que se debe al subárbol derecho del nodo A del subárbol derecho. |
 | Ahora realizamos una rotación RR (rotación en sentido antihorario) en el árbol completo, es decir, en el nodo A. nodo C ahora se ha convertido en el subárbol derecho del nodo B y el nodo A se ha convertido en el subárbol izquierdo de B. |
 | El factor de equilibrio de cada nodo ahora es -1, 0 o 1, es decir, BST ahora está equilibrado. |
P: Construya un árbol AVL que tenga los siguientes elementos
H, I, J, B, A, E, C, F, D, G, K, L
1. Insertar H, I, J
Al insertar los elementos anteriores, especialmente en el caso de H, el BST se desequilibra ya que el factor de equilibrio de H es -2. Dado que el BST está sesgado a la derecha, realizaremos una rotación RR en el nodo H.
El árbol de equilibrio resultante es:
2. Insertar B, A
Al insertar los elementos anteriores, especialmente en el caso de A, el BST se desequilibra ya que el factor de equilibrio de H e I es 2, consideramos el primer nodo del último nodo insertado, es decir, H. Dado que el BST de H está sesgado hacia la izquierda, Realizaremos la rotación LL en el nodo H.
El árbol de equilibrio resultante es:
3. Insertar E
Al insertar E, BST se desequilibra ya que el Factor de Equilibrio de I es 2, ya que si viajamos de E a I encontramos que está insertado en el subárbol izquierdo del subárbol derecho de I, realizaremos la Rotación LR en el nodo I. LR = rotación RR + LL
3 a) Primero realizamos la rotación RR en el nodo B
El árbol resultante después de la rotación RR es:
3b) Primero realizamos la rotación LL en el nodo I
El árbol equilibrado resultante después de la rotación LL es:
4. Inserte C, F, D
Al insertar C, F, D, BST se desequilibra ya que el Factor de Equilibrio de B y H es -2, ya que si viajamos de D a B encontramos que está insertado en el subárbol derecho del subárbol izquierdo de B, realizaremos Rotación RL en el nodo I. RL = rotación LL + RR.
4a) Primero realizamos la rotación LL en el nodo E
El árbol resultante después de la rotación LL es:
4b) Luego realizamos la rotación RR en el nodo B
El árbol equilibrado resultante después de la rotación RR es:
5. Insertar G
Al insertar G, BST se desequilibra ya que el Factor de Equilibrio de H es 2, ya que si viajamos de G a H, encontramos que está insertado en el subárbol izquierdo del subárbol derecho de H, realizaremos la Rotación LR en el nodo I. LR = RR + LL rotación.
5 a) Primero realizamos la rotación RR en el nodo C
El árbol resultante después de la rotación RR es:
5 b) Luego realizamos la rotación LL en el nodo H
El árbol equilibrado resultante después de la rotación LL es:
6. Insertar K
Al insertar K, BST se desequilibra ya que el factor de equilibrio de I es -2. Dado que el BST está sesgado a la derecha de I a K, realizaremos una rotación RR en el nodo I.
El árbol equilibrado resultante después de la rotación RR es:
7. Insertar L
Al insertar, el árbol L todavía está equilibrado ya que el factor de equilibrio de cada nodo ahora es -1, 0, +1. Por tanto, el árbol es un árbol AVL equilibrado.
