PadhaikoAll subjects

Past exam question: 2077 Chaitra (Regular), Q10(a)

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

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

Question

Explain balancing of B-tree with example.

Solution

How a B-Tree Maintains Perfect Balance: Unlike BSTs or AVL trees that balance via local rotations, a B-Tree of order stays perfectly height-balanced (all leaves at the exact same level) by allowing nodes to hold between and keys and growing upward from the root via node splitting:

  1. Every new key is inserted into a sorted leaf node.
  2. If the leaf remains within keys, no structural change occurs.
  3. If the leaf overflows ( keys), it splits at its median key into two half-full nodes and promotes the median key into its parent.
  4. If the parent overflows, splitting propagates upward; when the root splits, a new root with 1 key is created, increasing tree height uniformly across all paths.

Example (Order , Max 2 Keys per Node): Insert 10, 20, 30:

       [20]
      /    \
   [10]    [30]

Both leaves [10] and [30] remain at depth 1.

Answer:

A B-Tree stays balanced (all leaves at identical depth) through node splitting and upward median promotion: whenever an insertion causes a node to reach keys, its median key moves up to the parent and the remaining keys split evenly into two valid sibling nodes.

All past exam questions for Data Structure and Algorithms