Quasi-balanced Search Trees

In the following diagram, which we call a quasi-balanced search tree (QUBSET), every node represents a student. Each student has a name and each student has a student number, both of which are shown in    each node. Every diagram shown is structured by the same set of rules. You can assume for the whole    question that all names/IDs are unique.

Part A

i. If you remove the student IDs and only consider the names, what do you notice about the order/structure? Explain your answer. 0.5 marks

ii. If you remove the names and only consider the student IDs, what do you notice about the order/structure? Explain your answer. 0.5 marks

At the bottom of this page, we provide two examples that show what happens when we add a new student (node) to our diagram.

Part B

If we add the student Fin who has a student ID of 2, the QUBSET changes from left to right.

Write down all the missing steps in this process. You should provide just as much detail as the examples shown at the bottom. 2 marks

Part C

Given an arbitrary QUBSET, T , and a new student S, write a new function add_student(T , S) that adds  the new student to the diagram. Assume the operation is done in place (there should be no return value). You can assume Tname and Tid give the student name/ID respectively. T and S are of the same type and you can assume S has no children. Your pseudocode should look like the pseudocode that is given in      Lecture 9. 3 marks

Part D

We want the height of QUBSET to be as small as possible. Give an example of the worst case height when we add 5 students to an empty QUBSET. 1 mark

Part E

Suppose we have a group of n students that are listed in alphabetical order. If we add them to a binary   search tree (sorted just by name and ignoring their student IDs), it can be shown that it degenerates to a tree of height n. Explain why the QUBSET we have used in this question is likely to have a height much smaller than n. 1 mark

Example 1

We start with the following QUBSET

Now suppose we add Kevin who has a student ID of 20 to the QUBSET following the rule in part a) i.

After this, the tree does not follow the rule in part a) ii. We continue to update the diagram until it follows the QUBSET rule.