PadhaikoAll subjects

Past exam question: 2064 Jestha, Q6

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Balanced binary tree · Introduction to red-black tree · B-Tree: Need…

Question

What are the types of rotations used in balancing an AVL tree? Discuss the rules for deciding which type of rotation to use to restore the balance in AVL tree. For a given binary tree, construct an AVL tree showing its inorder traversal after every step.

[figure: binary tree rooted at A; A has left child B and right child C; B has left child D and right child E; E has left child F]

Solution

Four Types of AVL Rotations and Selection Rules: Let node be the nearest unbalanced ancestor with :

  1. LL (Single Right Rotation): and left child has (inserted into left subtree of left child).
  2. RR (Single Left Rotation): and right child has (inserted into right subtree of right child).
  3. LR (Left-Right Double Rotation): and left child has (inserted into right subtree of left child).
  4. RL (Right-Left Double Rotation): and right child has (inserted into left subtree of right child).

AVL Construction on Keys A, B, C, D, E, F (Level-Order):

  1. Insert A: Root A. Inorder: A.
  2. Insert B: Right of A. Inorder: A, B.
  3. Insert C: Right of B. RR (Left) Rotation at A root B (A, C).
    • Inorder: A, B, C.
  4. Insert D: Right of C. . Balanced.
    • Inorder: A, B, C, D.
  5. Insert E: Right of D. RR (Left) Rotation at C D replaces C with children C, E.
    • Inorder: A, B, C, D, E.
  6. Insert F: Right of E. RR (Left) Rotation at B: D becomes root, B becomes left child of D (with A left and C right), and E (with right F) is right child of D.
    • Inorder: A, B, C, D, E, F.
               D (0)
            /         \
         B (0)        E (-1)
         /   \            \
      A (0)  C (0)        F (0)
Answer:

AVL trees use LL, RR (single) and LR, RL (double) rotations selected by the signs of at the unbalanced node and its heavy child. Inserting A..F yields root D (left B with A, C; right E with F), with inorder A, B, C, D, E, F at completion.

All past exam questions for Data Structure and Algorithms