Solved

Binary Search Tree in Java

Posted on 2008-10-26
12
1,820 Views
Last Modified: 2013-11-23
Hi I have a binary search tree that I'm building.  I have an array of coordinates (Point objects) that I need to insert.  
The tree should branch based on the X-coordinate on even levels
The tree should branch based on the Y-coordinate on odd levels

I have an array that stores the coordinates, I have two methods to sort the array: xSort and ySort

I'm having a hard time trying to figure out how to build the tree.  Here is what I have so far, but it's probably not the way I should do it.
public Node buildTree(Point[] _arr, int left, int right){
        	if(_arr.length==0)
        		return null;
        	if(_arr.length==1)
        		root = new Node(_arr[0]);
        		return root;
        	else{
        		int median = (left + right)/2;
        		xSort(_arr);
        		root = new Node(_arr[median]);
        		root.left = buildTree(_arr, left, median+1);
        		root.right = buildTree(_arr, median+1, right);
        		return root;
        	}
        }

Open in new window

0
Comment
Question by:ubuntuguy
  • 5
  • 3
  • 3
  • +1
12 Comments
 
LVL 1

Accepted Solution

by:
Phasmid earned 250 total points
ID: 22808121
I think what you really need is an R-tree (since you are working in 2-dimensions -- B-trees are essentially one dimensional).  There are lots of resources on the web (some with Java code).  I suggest you try here: http://gis.umb.no/gis/applets/rtree2/jdk1.1/
0
 
LVL 1

Author Comment

by:ubuntuguy
ID: 22808367
Is this a good approach?  I get the following error:
Exception in thread "main" java.lang.Error: Unresolved compilation problem:
      Unreachable code
int median;
    	static Point [] leftPartition;
		static Point [] rightPartition;
        private static int calculateMedian(Point [] _arr){
        	if(_arr == null)
        		return -1;
        	if(_arr.length==0)
        		return 0;
        	else
        		return _arr.length/2;
        }
        private static Point[] calculateLeftPartition(Point [] _arr){
        	if(_arr == null)
        		return null;
        	else{
        		for(int i=0; i<calculateMedian(_arr); i++){
        			leftPartition[i] = _arr[i];
        		}
        	}
        	return leftPartition;
        }
        private static Point[] calculateRightPartition(Point [] _arr){
        	if(_arr == null)
        		return null;
        	else{
        		for(int i=calculateMedian(_arr)+1; i<_arr.length; i++){
        			rightPartition[i] = _arr[i];
        		}
        	}
        	return rightPartition;
        }
        
        
        public Node buildTree(Point[] _arr, Node _root){
        	if(_arr.length==0){
        		_root = new Node(null);
        		return _root;}
        	if(_arr.length==1){
        		_root = new Node(_arr[0]);
        		return _root;}
        	else{
        		xSort(_arr);
        		_root = new Node(_arr[calculateMedian(_arr)]);
        		ySort(calculateRightPartition(_arr));
        		ySort(calculateLeftPartition(_arr));
        		return buildTree(calculateLeftPartition(_arr), _root.left);
        		return buildTree(calculateRightPartition(_arr), _root.right);
        		}
        }
        
 
		public void xSort(Point [] arr){
			Arrays.sort(arr, new Point.CompX());
		}
		public void ySort(Point [] arr){
			Arrays.sort(arr, new Point.CompY());
		}

Open in new window

0
 
LVL 1

Expert Comment

by:Phasmid
ID: 22808390
Where did this bit of code come from?  Keep looking for Rtree (or R-tree) Java stuff on web until you find some code that works.
0
Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

 
LVL 59

Assisted Solution

by:Kevin Cross
Kevin Cross earned 250 total points
ID: 22808658
One thing is that you cannot instantiate Node.  If it is org.w3c.dom.Node or javax.xml.soap.Node, they are both Interfaces.  
0
 
LVL 59

Expert Comment

by:Kevin Cross
ID: 22808675
But, you may have another Node implementation that I don't have on my system, so to answer your question this is the code that is unreachable.

return buildTree(calculateLeftPartition(_arr), _root.left);
            return buildTree(calculateRightPartition(_arr), _root.right);

Once you have returned from the method, the second return cannot be reached.
0
 
LVL 1

Author Comment

by:ubuntuguy
ID: 22808787
Yes I'm using another Node implementation.  Why is
return buildTree(calculateLeftPartition(_arr), _root.left);
            return buildTree(calculateRightPartition(_arr), _root.right);
not reachable?
public class Node {
	
	public Point point;
	public Node left, right, parent;
	public int level;
	
	public Node(){  
		point = null;
		left = null;
		right = null;
                parent = null;
		level = 0;
	}
 
	public Node(Point _data){
		point = _data;
		point.x = _data.getX();
		point.y = _data.getY();
		left = null;
		right = null;
	}
	public Node(Point _data, Node _left, Node _right){
		point = _data;
		point.x = _data.getX();
		point.y = _data.getY();
		left = _left;
		right = _right;
	}
 
	public boolean isNull(Node _node){
		return _node.point==null;
	}
	
	public void setPoint(Point _point){
		this.point = _point;
	}
	public void setPoint(int a, int b){
		this.point.setX(a);
		this.point.setY(b);
		
	}
	public void setLeft(Node _node){
		this.left = _node;
	}
	public void setRight(Node _node){
		this.right = _node;
	}
	public void setLevel(int _level){
		this.level = _level;
	}
	
	public String toString(){
		if(this.point==null)
			return "Null Value";
		else 
			return this.point.toString();
	}
        }

Open in new window

0
 
LVL 1

Expert Comment

by:Phasmid
ID: 22808791
You can only make one return from a method.  If you want to return two separate objects, as it appears you might do here, then you would have to encapsulate them into a single object - or alternatively (and less elegantly) return them via method parameters.
0
 
LVL 59

Expert Comment

by:Kevin Cross
ID: 22808856
Thought I made that clear above, you can return from different control structures like you have under if...then...else.  But in each section (path of execution), once you have returned to the caller you no longer have thread of execution to do any more code much less return anything else.

You can alter your buildTree method to return a List<Node> object instead of a Node.  For most of the returns this will just be a single element or null, but you can also have it return your mutliple Nodes like this:

List<Node> list = new ArrayList<Node>();
list.add(node1);
list.add(node2);
return list;

You can use an array two, just think List<T> is a little more elogant. :)  If there are limitations on what API you can use for class then you can use a simple array of Node[].
0
 
LVL 59

Expert Comment

by:Kevin Cross
ID: 22808863
Looking at your code, you could just use this constructor:

public Node(Point _data, Node _left, Node _right){
            point = _data;
            point.x = _data.getX();
            point.y = _data.getY();
            left = _left;
            right = _right;
      }

It lets you define one Node object that contains the left Node and the right Node.  Then just return that Node.
0
 
LVL 1

Author Comment

by:ubuntuguy
ID: 22809373
Sorry guys, I've taken a different approach.  This is how I'm doing it now:  It works for just branching on the X-value.  I'm unsure how to branch by X on even levels and by Y on odd levels.  I have already define my methods that sort the array by X or by X.  
	public static Node buildTree(Point[] _arr, int _left, int _right){
		Node _t;
		int median;
		if(_right<_left)
			return null;
		if(_right==_left){
			_t = new Node(_arr[_left], null, null);
			return _t;
		}
		median = (_left+_right)/2;
		_t = new Node(_arr[median], null, null);
		_t.left = buildTree(_arr, _left, median-1);
		_t.right = buildTree(_arr, median+1, _right);
		_t.size = _right-_left+1;
		return _t;
	}

Open in new window

0
 
LVL 59

Expert Comment

by:Kevin Cross
ID: 22809428
Glad you found an approach that works.  But you did correct what we said which was the double return, so code should at least compile for you now.

Good luck.

Happy coding!

/kev
0
 
LVL 84

Expert Comment

by:ozo
ID: 22809442
0

Featured Post

Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
replace a word with other 1 44
oracle 11g 23 78
tomcat startup error 5 59
going to wrong jsp page 2 19
Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

786 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question