Develop methods to manipulate a binary search tree

Assignment Help JAVA Programming

Reference no: EM132109247

For this project you will develop methods to manipulate a Binary Search Tree. Binary Search Trees are a fundamental data structure in computing, and are the underlying structure of the TreeSet and TreeMap classes in the Java Collection Frameworks.

As before, we will be using the software of the BRIDGES project, which allows us to visualize the shape of the Binary Search Tree, and to see how it is altered by your methods.

The given source code includes a class called BinarySearchTree_Bridges. This class implements a Binary Tree, using the BSTElement class from Bridges to represent the nodes in the tree.

Similar to the TreeMap in the Java Collection Framework, each element in the tree will store both a key and the value associated with that key.

The given Driver source code uses Student objects as the test data, where the key associated with each Student is the name field. But any Object that is Comparable could also be stored in this Binary Search Tree.

The given BinarySearchTree_Bridges class has a method to search (i.e., "get") the tree for a given target key.

For this assignment you must complete the methods in the BinarySearchTree_Bridges class to perform the following operations.

- public void resetColor ( Color c )

This method traverses the entire tree and sets the color of each node to the specified color c.

- public E last ( Color c )

This method locates and returns the maximum value in the tree, and also changes the color of every node along the path from the root to the maximum value to be the specified color c.

-public E first ( Color c )

This method locates and returns the minimum value in the tree, and also changes the color of every node along the path from the root to the minimum value to be the specified color c.

- public int countAndColorMajors (Color c , String theMajor)

This method traverses the entire tree. Each node is examined, and if the value stored at that node is a Student object, and if the major field of that Student object equals the parameter theMajor, then that node is set to the specified color c. The total number of nodes that are colored by this method is returned. Note that this is the only method in this assignment that assumes that the data stored in the tree are Student objects. Your code can always check whether a value stored in the tree is a Students object using the instanceof operator in Java.

For example: if ( foo instanceof Student ) { .... }

- public void colorRange ( Color c, K minVal, K maxVal )

This method resets the color of every item in the tree whose key is greater-thanor-equal-to minVal, and less-than maxVal, to be the specified color c.

-public void deleteSmall ( K key )

This method removes from the tree every item whose key is less-than-or-equal-to the given parameter key. To remove these keys you should directly alter the pointers in the tree using setLeft and setRight methods to "splice out" the small values.

- public void deleteLarge ( K key )

This method removes from the tree every item whose key is greater-than the give parameter key.

- public E colorLower ( K key, Color c )

This method locates and returns the largest value in the tree that is strictly less than the given parameter key. If no such item exists, then the value null is returned. If the item exists, then the method changes the color of that node to be the specified color c.

- public E colorHigher ( K key, Color c )

This method locates and returns the smallest value in the tree that is strictly greater than the given parameter key. If no such item exists, then the value null is returned. If the item exists, then the method changes the color of that node to be the specified color c.

As always, you should implement all these methods in the most efficient manner possible. Your code should not traverse more nodes in the tree than is necessary.

The given Driver code will test your methods and display the tree that is produced by your code. You should create additional test cases to insure that your code is correct, instead of relying only on the given test cases.

Reference no: EM132109247

Questions Cloud

Draw an edgeworth box diagram : Draw an Edgeworth box diagram to show whether this allocation of resources is efficient. If it is explain why.

Converting ascii strings received from the uart : Converting ASCII strings received from the UART into an integer value that is passed to a provided print function.

Simulating a supermarket self-service checkout : Create an activity chart which describes the behaviour of the checkout system - Create a computer program that allows a user to interactively check out a number

What proportion of the figures are triangles : (a) What proportion of the figures are triangles? (b) If a circle is randomly drawn, what is the probability that it is red?

Develop methods to manipulate a binary search tree : Develop methods to manipulate a Binary Search Tree. Binary Search Trees are a fundamental data structure in computing.

Compute the expected value of the number : If the first ball drawn is marked 3, compute the expected value of the number drawn from the second drawing.

Identify functional dependencies and derive candidate keys : Display the origin, destination, departure time from origin, and arrival time at destination for all flights that occur in the same time zone.

Buying country make before placing an order : So, what arrangements might the buying country make before placing an order with the USA country?

Relationship between a currency value : Is there a relationship between a currency's value and its balance-of-trade? (Effectively defend your answer with citations).

User Account

All Pages