PadhaikoAll subjects

Past exam question: 2078 Baishakh (Back), Q10

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

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

Question

Define red-black tree with example. Construct an AVL tree by inserting following elements in given order: 63, 9, 19, 27, 18, 108, 99, 81, 41.

Solution

Definition and Example of Red-Black Tree: A Red-Black Tree is a self-balancing binary search tree in which each node carries a color bit (RED or BLACK) satisfying five invariants:

  1. Every node is either RED or BLACK.
  2. The root is BLACK.
  3. Every NULL leaf (NIL) is BLACK.
  4. No two RED nodes are adjacent (a RED node's children are both BLACK).
  5. Every simple path from any node to its descendant NULL leaves has the same number of BLACK nodes (black-height).

Example (keys 10, 5, 15, 2):

        10 (B)
       /      \
     5 (B)    15 (B)
     /
   2 (R)

Every path from 10 to NULL passes through exactly 2 black nodes.

AVL Tree Construction — Insertions 63, 9, 19 (LR Rotation at 63):

        19 (0)
       /      \
     9 (0)   63 (0)

Insertions 27, 18, 108, 99, 81 (LL Rotation at 108):

              19 (-1)
            /         \
         9 (-1)       63 (-1)
           \         /       \
          18 (0)  27 (0)     99 (0)
                            /     \
                         81 (0)  108 (0)

Insertion 41:

                 19 (-1)
               /         \
            9 (-1)       63 (0)
              \         /       \
             18 (0)  27 (-1)    99 (0)
                        \       /     \
                       41 (0) 81 (0) 108 (0)
Answer:

All past exam questions for Data Structure and Algorithms