Preguntas de práctica sobre Altura equilibrada/Árbol AVL

El árbol AVL es un árbol de búsqueda binaria con la propiedad adicional de que la diferencia entre la altura del subárbol izquierdo y el subárbol derecho de cualquier Node no puede ser más de 1. Aquí hay algunos puntos clave sobre los árboles AVL :

• Si hay n Nodes en el árbol AVL, la altura mínima del árbol AVL es piso (log ₂ n).
• Si hay n Nodes en el árbol AVL, la altura máxima no puede exceder 1.44*log ₂ n.
• Si la altura del árbol AVL es h, el número máximo de Nodes puede ser 2 ^h+1 – 1.
• El número mínimo de Nodes en un árbol con altura h se puede representar como:
  N(h) = N(h-1) + N(h-2) + 1 para n>2 donde N(0) = 1 y N(1 ) = 2.
• La complejidad de buscar, insertar y borrar en el árbol AVL es O(log n).

Hemos discutido tipos de preguntas basadas en árboles AVL.

Tipo 1: relación entre el número de Nodes y la altura del árbol AVL:
dada la cantidad de Nodes, se puede hacer la pregunta para encontrar la altura mínima y máxima del árbol AVL. Además, dada la altura, se puede pedir el número máximo o mínimo de Nodes.

Que – 1. ¿Cuál es la altura máxima de cualquier árbol AVL con 7 Nodes? Suponga que la altura de un árbol con un solo Node es 0.
(A) 2
(B) 3
(C) 4
(D) 5

Solución: Para encontrar la altura máxima, los Nodes deben ser mínimos en cada nivel. Suponiendo
que la altura sea 2, número mínimo de Nodes requeridos:
N(h) = N(h-1) + N(h-2) + 1
N(2) = N(1) + N(0) + 1 = 2 + 1 + 1 = 4.
Significa que la altura 2 se logra utilizando un mínimo de 4 Nodes.

Suponiendo que la altura es 3, se requiere un número mínimo de Nodes:
N(h) = N(h-1) + N(h-2) + 1
N(3) = N(2) + N(1) + 1 = 4 + 2 + 1 = 7.
Significa que la altura 3 se logra utilizando un mínimo de 7 Nodes.

Por lo tanto, usando 7 Nodes, podemos lograr una altura máxima de 3. A continuación se muestra el árbol AVL con 7 Nodes y una altura de 3.

Que – 2. ¿Cuál es la altura posible del árbol AVL en el peor de los casos?
(A) 2*logn
(B) 1,44*log n
(C) Depende de la implementación
(D) θ(n)

Solución: La altura posible del árbol AVL en el peor de los casos con n Nodes es 1.44*logn. Esto se puede verificar utilizando el árbol AVL que tiene 7 Nodes y una altura máxima.

Verificando la opción (A), 2*log7 = 5.6, sin embargo, la altura del árbol es 3.
Verificando la opción (B), 1.44*log7 = 4, que está cerca de 3.
Verificando la opción (D), n = 7, sin embargo, la altura del árbol es 3.
De estas, la opción (B) es la mejor respuesta posible.

Tipo 2: Basado en la complejidad de inserción, eliminación y búsqueda en el árbol AVL –

Que – 3. ¿Cuál de las siguientes es VERDADERA?
(A) El costo de buscar un árbol AVL es θ(log n) pero el de un árbol binario de búsqueda es O(n)
(B) El costo de buscar un árbol AVL es θ(log n) pero el de un binario completo árbol es θ(n log n)
(C) El costo de buscar un árbol de búsqueda binario es O(log n ) pero el de un árbol AVL es θ(n)
(D) El costo de buscar un árbol AVL es θ(n) log n) pero el de un árbol de búsqueda binario es O(n)

Solución: Complejidad temporal de búsqueda, inserción y eliminación del árbol AVL = O(logn). Pero un árbol de búsqueda binaria puede ser un árbol sesgado, por lo que en el peor de los casos, la complejidad de búsqueda, inserción y eliminación de BST = O (n).

Que – 4. El peor tiempo de ejecución para buscar un elemento en un árbol de búsqueda binario equilibrado con n*2^n elementos es

Solución: El tiempo necesario para buscar un elemento es Θ(logn) donde n es el número de elementos en el árbol AVL.
Como el número de elementos dado es n*2^n, la complejidad de la búsqueda será Θ(log(n*2^n)) que se puede escribir como:

= Θ(log(n*2^n))
= Θ(log(n)) + Θ(log(2^n))
= Θ(log(n)) + Θ(nlog(2))
= Θ(log(n)) + Θ(n)

Como logn es asintóticamente más pequeño que n, Θ(log(n)) + Θ(n) se puede escribir como Θ(n) que coincide con la opción C.

Tipo 3: Inserción y eliminación en el árbol AVL:
la pregunta se puede hacer en el árbol resultante cuando las claves se insertan o eliminan del árbol AVL. Es necesario realizar las rotaciones adecuadas si se altera el factor de equilibrio.

Que – 5. Considere el siguiente árbol AVL.

¿Cuál de los siguientes es un árbol AVL actualizado después de la inserción de 70?

(A)

(B)

(C)

(D) Ninguno

Solución: Primero se inserta el elemento de la misma manera que BST. Por lo tanto, después de la inserción de 70, BST se puede mostrar como:

Sin embargo, el factor de equilibrio se altera y requiere la rotación de RL. Para eliminar la rotación RL, primero se convierte en rotación RR como:

Después de eliminar la rotación RR, el árbol AVL generado es el mismo que la opción (C).