Binary Search Tree (using C++). Write a program that a company can use to keep u

Question

Binary Search Tree (using C++).

Write a program that a company can use to keep up with the efficiency of its employees. The company keeps a record of mistakes made by each employee. If five mistakes are made by an employee, the employee is fired. The company has a maximum of 20 employees. Each employee has a unique identification number between 10 and 40. An employee is represented by an ID number and a counter to count the number of mistakes that the employee has made. Write a program to simulate this process by using the following guide lines. Allow your program to randomly generate the identifications for each employee between 10 and 30. The first time an identifications number is generated the person is lured with a count of zero mistakes. If the same identification number is generated again, increment the counter for the employee's mistakes. Once the person makes 5 mistakes fire the person. Use binary search trees to keep up with the employees. A person is hired by placing the information about the person (identification number and zero mistakes) on an employee binary search tree. A person is fired by removing the information about the person from the employee binary search tree and placing the information on a fired binary search tree. Both binary search trees are ordered by the employee's identification number. Allow your program to randomly generate ID numbers100 times. (Use the C++ rand() function) Your program should do the following: Print out a numerically ordered list of all identification numbers of employees along with the number of mistakes of each employee from the employee binary search tree. Remove all employees fiom the employees binary search tree with 5 or more mistakes Print out the content of the employees binary search tree after the fired employees have been removed. Print out a numerically ordered list of the identification numbers of the fired employees along with the number of mistakes for each employee on the fired binary search tree. Use one of the following definitions for your binary search tree: The following definition for the binary search tree modifies the node class to hold the two values: The following definition for the binary search tree using a struct to hold the two values:

Explanation / Answer

Binary Search Tree

Deletion in BST

Let x be a value to be deleted from the BST and let X denote the node containing the value x. Deletion of an element in a BST again uses the BST property in a critical way. When we delete the node X containing x, it would create a "void" that should be filled by a suitable existing node of the BST. There are two possible candidate nodes that can fill this void, in a way that the BST property is not violated: (1). Node containing highest valued element among all descendants of left child of X. (2). Node containing the lowest valued element among all the descendants of the right child of X. In case (1), the selected node will necessarily have a null right link which can be conveniently used in patching up the tree. In case (2), the selected node will necessarily have a null left link which can be used in patching up the tree. Figure 1.2 illustrates several scenarios for deletion in BSTs.

C++ Program example:

Figure 1.1: An example of a binary search tree

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.