Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 2011, Assignment #2

1.  (100 points) Implement a binary search tree to store students of the University. The keys are the students’names, and a surname is listed before a given name.  Your implementation should allow the user to find information about a student quickly.

The first part is about the shape of the tree you have built.  Although we do not have a definitive measure for how close a binary tree is to a perfect one, the following three numbers give some partial information.

• The largest difference between the depths of the two subtrees of a node.

• The largest difference between the sizes of the two subtrees of a node.

• The total number of nodes that have only one child.

For example, they are 1, 2, and 0 for tree (a) and 3, 3, and 3 for tree (b).

(a)                                                                   (b)

The second part is about search. It supports three ways of search.

• Search for a student with a specified name.  It must be an exact match of the full name.  If there are multiple students of this name, you may return any of them.

• Search for all the students with the specified surname.  For simplicity, let us treat the first word as the surname. (Sorry if your surname is “Au Yeung.”)

• Search all the students who are taking a certain class.

Implement the following seven methods.  Do not modify their signatures. You may add as many additional private helper methods as needed.

public   void   insert(Student   s)

public   int  maxDepthDiff()

public   int  maxSizeDiff()

public   int   nodesWithOneChild()

public   Student   searchFullname(String   name)         public   Student[]   searchSurname(String   surname) public   Student[]   searchClass(String[]   roster)

Write the running time as a function of d (the depth of the tree), n (the total number of students), and c (the number of students in a class). Generally, c < ^n.

You get 10 bonus points if your implementation is self-balancing.