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

Considere las siguientes funciones de rotación a la izquierda y rotación a la derecha comúnmente utilizadas en BST autoajustables

T1, T2 and T3 are subtrees of the tree rooted with y (on left side) 
or x (on right side)           
                y                               x
               / \     Right Rotation          /  \
              x   T3   – - – - – - – >        T1   y 
             / \       < - - - - - - -            / \
            T1  T2     Left Rotation            T2  T3

¿Cuál de los siguientes es el límite superior más ajustado para las operaciones de rotación a la izquierda y rotación a la derecha?

(A) O(1)
(B) O(Logn)
(C) O(LogLogn)
(D) O(n)

Respuesta: (A)
Explicación: Las operaciones de rotación (rotación izquierda y derecha) toman un tiempo constante ya que solo unos los punteros se están cambiando allí. Las siguientes son implementaciones en C de rotación a la izquierda y rotación a la derecha

// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct node *rightRotate(struct node *y)
{
    struct node *x = y->left;
    struct node *T2 = x->right;
   
    // Perform rotation
    x->right = y;
    y->left = T2;
   
    // Update heights
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;
   
    // Return new root
    return x;
}
   
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct node *leftRotate(struct node *x)
{
    struct node *y = x->right;
    struct node *T2 = y->left;
   
    // Perform rotation
    y->left = x;
    x->right = T2;
   
    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;
   
    // Return new root
    return y;
}

Cuestionario de esta pregunta