Question

2 Consider the sequence of keys (5,16,22,45,2,10,18,30,50,12,1). Draw the result of inserting entries with these keys (in the given order) into a. An initially empty (2,4) tree. b. An initially empty red-black tree.

Answer 1

Answer:

A) (2,4) tree

• Insertion of  key 45 makes key unbalanced and this is because it violates the 2,4 tree so we split the node

• insertion of key 10 makes key unbalanced and this is because it violates the 2,4 tree so we split the node

B) Red-black tree

Explanation:

The diagrams for the solutions are attached showing the results of inserting entries