Please help with 2-d Trees

Hi everybody I'm kinda of stuck with the add method at the end I attach want I have done so any help will be highly appreciated, thanks.

Implement a data structure that supports two dimensional range queries using a 2-d tree. A 2-d trees stores pairs of items.A 2-d tree is like a binary search tree, except that at even levels branching is done with respect to the first item in the pair, and at odd levels, branching is done with respect to the second item in the pair.

Testing the Class

Test your implementation with this program.
[code]

import cop3530.TwoDimensionSearcher;
import cop3530.TwoDTree;
import java.util.List;
import java.util.Iterator;
import java.util.Random;

class Assign4
{
public static final int MAX = 500000;

public static void main( String [ ] args )
{
long startTime = System.currentTimeMillis( );

TwoDimensionSearcher t = new TwoDTree( );
Random r = new Random( 3737 );

for( int i = 0; i < MAX; i++ )
t.add( t.makePair( new Integer( r.nextInt( MAX ) ),
new Integer( r.nextInt( MAX ) ) ) );

System.out.println( "Size is: " + t.size( ) );


TwoDimensionSearcher.Pair ll = t.makePair( new Integer( (int) (MAX*.49) ),
new Integer( (int) (MAX*.49) ) );

TwoDimensionSearcher.Pair ur = t.makePair( new Integer( (int) (MAX*.51) ),
new Integer( (int) (MAX*.51) ) );

List rangeResult = t.getItemsInInterval( ll, ur );
System.out.println( rangeResult.size( ) + " items in interval" );

Iterator itr = rangeResult.iterator( );
while( itr.hasNext( ) )
System.out.println( itr.next( ) + " " );

System.out.println( );
System.out.println( "Items of form [x,x] is: " );

for( int i = 0; i < MAX; i++ )
{
Integer ii = new Integer( i );
if( t.contains( t.makePair( ii, ii ) ) )
System.out.println( "[" + i + "," + i + "]" );
}

long endTime = System.currentTimeMillis( );

System.out.println( "Elapsed time: " + ( endTime - startTime ) );
}
}




[/code]


Warning: you should probably write another program to make sure everything works.

Requirements
Here is the class interface for cop3530.TwoDimensionSearcher. You will implement your class as cop3530.TwoDTree. You may not change the interface in any way whatsoever. You should not add any new public methods to your implementation, but you can add private methods as needed to avoid replication of code.

[code]
package cop3530;

import java.util.List;

public interface TwoDimensionSearcher
{
void makeEmpty( );
boolean isEmpty( );
boolean add( Pair x );
int size( );
List getItemsInInterval( Pair lowerLeft, Pair upperRight );
boolean contains( Pair x );
Pair makePair( Object first, Object second );

public interface Pair
{
Object getFirst( );
Object getSecond( );
}
}

[/code]

Here is the rough outline of the implementation:

[code]
package cop3530;

import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;

public class TwoDTree implements TwoDimensionSearcher
{
private static class LocalPair implements TwoDimensionSearcher.Pair
{ /* Implementation not shown */ }

private static class Node
{ /* Implementation not shown */ }

public TwoDTree( )
{ /* Implementation not shown */ }

public TwoDTree( Comparator c1, Comparator c2 )
{ /* Implementation not shown */ }

public void makeEmpty( )
{ /* Implementation not shown */ }

public Pair makePair( Object first, Object second )
{ /* Implementation not shown */ }

public boolean isEmpty( )
{ /* Implementation not shown */ }

public int size( )
{ /* Implementation not shown */ }

// You MUST keep this implementation
public boolean contains( Pair x )
{ return getItemsInInterval( x, x ).size( ) == 1; }

public boolean add( Pair x )
{
int oldSize = size( );
root = add( x, root, true ); // call private recursive routine
return size( ) != oldSize;
}

private Node add( Pair x, Node t, boolean isEven )
{ /* Implementation not shown */ }

public List getItemsInInterval( Pair lowerLeft, Pair upperRight )
{ /* Implementation not shown;
may involve use of private recursive routine */ }

public String toString( )
{ /* Implementation not shown;
may involve use of private recursive routine */ }

private int size;
private Node root;
private Comparator cmp1;
private Comparator cmp2;
}


[/code]

In implementing this interface you must use a tree of Pairs as the private data (shown as root), along with a size field. You should not need to throw any runtime exceptions.

Observe that signatures all refer to objects of type Pair, which in turn refers to two Objects. The interface defines a nested interface Pair, and the implementation class defines a private class called LocalPair that implements Pair. A TwoDTree object is created by supplying two java.util.Comparator function objects (one for even levels, one for odd levels); if none is given, it is assumed that the items in the pairs all implement the java.lang.Comparable interface and can be compared by calling compareTo.

It is very important that you optimize your getItemsInInterval method to avoid going down branches of the tree that cannot possibly produce any items. If you are careful, your algorithm will run in average time that is O( K + log N ) rather than O( N ), where K is the number of items that are found. In particular, this will make your contains method (in which K is 1) logarithmic, on average. If you are careless, the test program will require significant amounts of time.


This is what I have done so far:

[code]
package cop3530;

import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;

public class TwoDTree implements TwoDimensionSearcher
{
private int size;
private Node root;
private Comparator cmp1;
private Comparator cmp2;


public TwoDTree( )
{
setRoot(null);
}

public TwoDTree( Comparator c1, Comparator c2 )
{
/* Implementation not shown */
}

private Node getRoot()
{
return root;
}
private void setRoot(Node r)
{
root = r;
}

private static class LocalPair implements TwoDimensionSearcher.Pair
{

Object first;
Object second;

public LocalPair(Object of, Object os)
{
first = of;
second = os;
}

public Object getFirst()
{
return first;
}

public Object getSecond()
{
return second;
}
/* Makes the elements look like this (x,x)*/
public String toString()
{
return "(" + first + "," + second + ")";
}
}

private static class Node
{
Object data;
Node left,right;

public Node()
{
data = null;
left = right = null;
}
public Node(Object d)
{
data = d;
left = right = null;
}
public void setLeft(Node l)
{
left = l;
}
public void setRight(Node r)
{
right = r;
}
public void setData(Object d)
{
data = d;
}
public Node getLeft()
{
return left;
}
public Node getRight()
{
return right;
}
public Object getData()
{
return data;
}
public String toString()
{
return ""+data;
}

}

public void makeEmpty( )
{
root = null;
}

public Pair makePair( Object first, Object second )
{
LocalPair myLocalPair = new LocalPair(first,second);
myLocalPair.first = first;
myLocalPair.second = second;
return myLocalPair;
}

public boolean isEmpty( )
{
return root == null;
}

public int size( )
{
return size;
}

// You MUST keep this implementation
public boolean contains( Pair x )
{
return getItemsInInterval( x, x ).size( ) == 1;
}

public boolean add( Pair x )
{
int oldSize = size( );
root = add( x, root, true ); // call private recursive routine
return size( ) != oldSize;
}

private Node add( Pair x, Node t, boolean isEven )
{
t = new Node();

if(isEven == true)
t.setRight(x);
else
t.setLeft(x);
}

public List getItemsInInterval( Pair lowerLeft, Pair upperRight )
{ /* Implementation not shown;
may involve use of private recursive routine */ }

public String toString( )
{ /* Implementation not shown;
may involve use of private recursive routine */ }

}
[/code]

Comments

  • Would you ming posting the add-method itself? I haven't found it in the code you posted (didn't look very carefully, though...).

    It's always a good idea to post a little bit and ask very specific question. If more info is needed to answer it, we'll let you know, be so sure about it :-)!


    Kind Regards
    Konrad
    ----------------------------
    (+46/0) 708-70 73 92
    [email protected]
    http://konrads.webbsida.com

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion