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; } }

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/

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(); } }

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.

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[].

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; }

Contextual Guidance at the moment of need helps your employees adopt to new software or processes instantly. Boost knowledge retention and employee engagement step-by-step with one easy solution.

Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…

Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…

This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.