Graded Discussion Board (GDB) of CS301 will be opened on Thursday, February 19, 2015 and it will close on Friday, February 20, 2015 11:59 PM.
GDB Scenario: Suppose you are hired as a software engineer by a leading software company and assigned a task to store employees' records alphabetically based on employees names. Your application should allow records to be inserted, deleted, and searched by name. The company’s main concern is to perform efficient searching on employees’ record to check for employees’ performance. For this, Binary Search is a good option. But there is a problem in BST that it does not deal with duplicate values as its formal definition says “If an element is greater than its root, it will go on its right side; and if it is less than its root, it will go on its left side”. This definition does not deal with duplicate values. But, in given scenario, as more than one employee may have the same name, so your BST should be able to deal with duplicate values too. Now consider that, you have the following options to change BST definition to accommodate duplicate values too:
- If an element is greater than root, it will go on its right side, and if it is less than root, it will go on its left side; otherwise, it may go on either right or left side of root.
- Use an array with each node to store duplicate entries.
GDB Question: Your task is to analyze costs and benefits of using above proposed alterations in BST definition with respect to time and memory for the given scenario.
