Past exam question: 2078 Baishakh (Back), Q10
Open in the Padhaiko appQuestion
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:
- Every node is either
REDorBLACK. - The root is
BLACK. - Every
NULLleaf (NIL) isBLACK. - No two
REDnodes are adjacent (aREDnode's children are bothBLACK). - Every simple path from any node to its descendant
NULLleaves has the same number ofBLACKnodes (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):
- Insert
63: root(63). - Insert
9: left child of63. . - Insert
19: right child of9. LR Rotation (left-rotate9, right-rotate63):
19 (0)
/ \
9 (0) 63 (0)Insertions 27, 18, 108, 99, 81 (LL Rotation at 108):
- Insert
27: left child of63. . - Insert
18: right child of9. . - Insert
108: right child of63. . - Insert
99: left child of108. . - Insert
81: left child of99.- LL (Single Right) Rotation at
108:99becomes parent of81and108.
- LL (Single Right) Rotation at
19 (-1)
/ \
9 (-1) 63 (-1)
\ / \
18 (0) 27 (0) 99 (0)
/ \
81 (0) 108 (0)Insertion 41:
- Insert
41: right child of27.- , , . All (no rotation needed).
19 (-1)
/ \
9 (-1) 63 (0)
\ / \
18 (0) 27 (-1) 99 (0)
\ / \
41 (0) 81 (0) 108 (0)Answer:
- Red-Black Tree: A self-balancing BST maintaining height via node colors and black-height invariants.
- Final AVL Tree: Root 19, left subtree 9 (right 18), right subtree 63 (left 27 with right 41; right 99 with children 81 and 108).