Estructuras de datos | Árboles de búsqueda binarios equilibrados | Pregunta 5

Considere el siguiente árbol AVL.

         60
      /     \  
    20      100
           /   \
         80    120     

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

A
        70
      /    \  
    60      100
   /       /    \
 20       80    120 

B
        100
      /    \  
    60      120
   /  \     /  
 20   70   80   


C
        80
      /    \  
    60      100
   /  \       \
 20   70      120

D
        80
      /    \  
    60      100
   /       /   \
 20      70    120  

(A) A
(B) B
(C) C
(D) D

Respuesta: (C)
Explicación: consulte los siguientes pasos para la inserción de AVL.

Árbol AVL | Juego 1 (inserción)

After insertion of 70, tree becomes following
         60
      /     \  
    20      100
           /   \
         80    120     
        /
       70

Partimos de 50 y viajamos hacia arriba. Seguimos viajando hacia arriba hasta que encontramos un Node desequilibrado. En el caso anterior, llegamos al Node 60 y vemos que 60 se desequilibró después de la inserción y este es el caso derecho izquierdo . Así que tenemos que aplicar dos rotaciones

         60                               60                            80
      /     \       Right Rotate(100)  /      \     Left Rotate(60)   /    \
    20      100    -----------------> 20        80 ---------------> 60      100 
           /   \                              /   \                /  \        \
         80    120                          70     100            20   70       120  
        /                                            \    
      70                                             120 

Cuestionario de esta pregunta