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;
}
}
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());
}
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();
}
}
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;
}
If you are experiencing a similar issue, please ask a related question
Join the community of 500,000 technology professionals and ask your questions.
Connect with top rated Experts
15 Experts available now in Live!