Let r1, r2, r3, ... ,r12 be an ordered list of 12 records which are stored at the internal nodes of a binary search tree T.

(a) Explain why record rₑ is the one that will be stored at the root (level 0) of the tree T. [1]

(b) Construct the tree T showing where each record is stored. [3]

(c) Let S = {r1, r2, r3, ... ,r12 } denote the set of records stored at the internal nodes of T, and define a relation R on S by:
r_a R r_b, if r_a and r_b are stored at the same level of the tree T.

i. Show that R is an equivalence relation. [5] [1]

ii. List the equivalence class containing r₇. [2]