PadhaikoAll subjects

Past exam question: 2062 Baishakh (Regular / Back), Q5

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

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

Question

Define B-tree. Create AVL tree using AVL balancing algorithm for the given sequence of data. 14, 12, 8, 18, 20, 23, 44, 52. Show the steps of balancing clearly.

Solution

Definition of B-Tree: A B-Tree of order is a self-balancing multi-way search tree in which every node has at most children and sorted keys, every internal node (except root) has at least children, the root has at least 2 children (unless a leaf), and all leaves appear at the exact same level.

AVL Construction — 14, 12, 8 (LL Rotation) and 18, 20 (RR Rotation):

           12 (-1)
          /       \
        8 (0)     18 (0)
                 /     \
              14 (0)   20 (0)

Insert 23 (RR Rotation at 12), 44 (RR Rotation at 20), and 52:

                   18 (-1)
                /          \
            12 (0)         23 (-1)
            /    \         /     \
          8 (0)  14 (0)  20 (0)  44 (-1)
                                     \
                                     52 (0)
Answer:

Final AVL tree has root 18, left subtree 12 (8, 14), and right subtree 23 (left 20; right 44 with right child 52).

All past exam questions for Data Structure and Algorithms