Description
This problem can be found in Chapter 26 of the 5th edition or Chapter 25 of the 4th edition as Project 12.
A 2D tree is a binary search tree in which each node contains a 2D point and holds the x and y coordinates of that node. 2D tree generalizes a binary search tree in that it positions each node according to either the x or y coordinates of its data point. The coordinate choice depends on the level at which the node is added into the tree. The first point you add into an empty tree is placed into a node that becomes the tree’s root. If the next point to be added has an x-coordinate that is less than the x-coordinate of the point in the root, you place the new point into the left child of the root. Otherwise, you place it into root’s right child. Insertions at the next level compares y-coordinates; insertion at level 4 compares x-coordinates, and so on. A break down of the tree is the following
For example, suppose we want to add the points (50,40),(40,70),(80,20),(90,10
• The first point becomes the root node.
• To add (40,70), you compare 40, the point’s x-coordinate, with 50, the x-coordinate of the root. Since 40 is less than 50, you move to the left. The left child of root is null so the new point goes into the left child of the root.
• To add (80,20), you compare 80 with 50, the x-coordinates of the root node. Since 80 is greater than or equal to 50, you move to the right. The right child of the root is null, so new node (80,20) is placed into the right child of the root.
• To add the next point, (90,10), you compare 90 with the x-coordinate of the root node. 90 is greater than or equal to 50, so you move to the right child and compare the y-coordinate with the right child. 10 is less than 20, the y-coordinate of the root’s right child. Hence, you move to the left. The left child of (80,20) is null, hence, the new node (90,10) is added as the left child of (80,20)
• To add the next point (60,30), you compare 60 with x-coordinate of the root. 60 is greater than or equal to 50, so you move to the right. Then you compare the y coordinates of (60,30) with y-coordinate of (80,20). 30 ≥ 20 so you move to the right. Since the right of (80, 20) is null, (60, 30) gets placed there.
If we were to add yet another point (70, 50) then we go through the same process.
• Start at the root and compare x-coordinates. 70 ≥ 50 so we move to the right.
• Compare the y-coordinate with (80, 20). 50 ≥ 20 so we move to the right.
• Compare the x-coordinate with (60, 30). 70 ≥ 60 so we move to the right.
• The right is null so we add our node there.
Another thing to note is that duplicates are not allowed. You can either check as you go if you come across a point whose coordinate values are the same as the coordinate values of the new point then throw an IllegalArgumentException. You can alternatively call your contains method before the add.
In summary, you need to alternate between x and y checks at every level starting with x at the root.
The file TwoDTree.java attached to this assignment provides a skeleton for implementation of a 2-d tree. This file contains a nested class TwoDTreeNode which represents a node in the TwoDTree and holds the x and y coordinates for the node as well as references to its left and right children.
Your job is to implement two methods in this file:
1. public void add(Point newPoint) : This method adds a new node with coordinates (x,y), represented as a Point object, newPoint, to the 2d tree. Duplicate nodes are not allowed in the tree. Throw an illegal argument exception if a duplicate node is attempted to be added. Don’t forget to increase size.
2. public boolean contains(Point p): This method returns true if a node with given Point exists in the TwoDTree else returns false.
I have also provided a helper method levelOrderPrint to print the level-order traversal of the tree. This method helps you test your add method and view a level order traversal of the tree after adding nodes to it. You can use any additional helper method you want.
Hints:
• For implementing the add method, you can use the add(T obj) method in the GenericBinarySearchTree .java file (provided under “source code” section on blackboard) as an example and modify it to fit the specification of this problem. For example, to find the insertion point for a new node, you start from the root node and go down the tree. At each point you decide to go left or right based on comparing the current node with x or y coordinate. The choice of which coordinate to use depends on the level in which you are performing the comparison. At root level (level 0) the x coordinate is used for comparison; at next level (level 1) the y coordinate is used for comparison, at level 2, the x coordinate is used for comparison, and so on.
• Once you implement the add method, the contain method should be easy to implement. You simply follow the same process. To find a given node, you start at the root node and go down the tree to find the node. At each point you compare the x or y coordinate with the current node and decide to go left or right. The choice of coordinate depends on the level on which you are doing the comparison.
• Please make sure to test your method for various test cases. I made up a small sample main method. The main method and the result of its run is shown below:
What you need to turn in:
1. The modified TwoDTree.java class including the above two methods.
2. A document containing the Analysis of the time efficiency of your methods in two cases: case1- The 2-d binary search tree is balanced and case 2- the 2-d binary search tree is not balanced.
Grading Rubric
Add method works correctly for all test cases 42.5
Contains method works correctly for all test cases 42.5
Analysis of Time efficiency of your methods when the tree is balanced and when the tree is imbalanced. You should explain what is worst case running time in each case. 15
Total 100
