Hello,
I need help with the print function. Everything works fine, but when I run the that function it gives a stack over flow problem. I do not understand why when this print function works fine with the other binary search tree implementations.
public class SplayTree<AnyType extends Comparable<? super AnyType>>
{
public SplayTree( )
{
nullNode = new BinaryNode<AnyType>( null );
nullNode.left = nullNode.right = nullNode;
root = nullNode;
}
private BinaryNode<AnyType> newNode = null; // Used between different inserts
public void insert( AnyType x )
{
if( newNode == null )
newNode = new BinaryNode<AnyType>( null );
newNode.element = x;
if( root == nullNode )
{
newNode.left = newNode.right = nullNode;
root = newNode;
}
else
{
root = splay( x, root );
int compareResult = x.compareTo( root.element );
if( compareResult < 0 )
{
newNode.left = root.left;
newNode.right = root;
root.left = nullNode;
root = newNode;
}
else
if( compareResult > 0 )
{
newNode.right = root.right;
newNode.left = root;
root.right = nullNode;
root = newNode;
}
else
return; // No duplicates
}
newNode = null; // So next insert will call new
}
public void remove( AnyType x )
{
BinaryNode<AnyType> newTree;
// If x is found, it will be at the root
root = splay( x, root );
if( root.element.compareTo( x ) != 0 )
return; // Item not found; do nothing
if( root.left == nullNode )
newTree = root.right;
else
{
// Find the maximum in the left subtree
// Splay it to the root; and then attach right child
newTree = root.left;
newTree = splay( x, newTree );
newTree.right = root.right;
}
root = newTree;
}
public AnyType findMin( ) throws Exception
{
if( isEmpty( ) )
throw new Exception( );
BinaryNode<AnyType> ptr = root;
while( ptr.left != nullNode )
ptr = ptr.left;
root = splay( ptr.element, root );
return ptr.element;
}
public AnyType findMax( ) throws Exception
{
if( isEmpty( ) )
throw new Exception( );
BinaryNode<AnyType> ptr = root;
while( ptr.right != nullNode )
ptr = ptr.right;
root = splay( ptr.element, root );
return ptr.element;
}
public boolean contains( AnyType x )
{
if( isEmpty( ) )
return false;
root = splay( x, root );
return root.element.compareTo( x ) == 0;
}
public void makeEmpty( )
{
root = nullNode;
}
public boolean isEmpty( )
{
return root == nullNode;
}
private BinaryNode<AnyType> header = new BinaryNode<AnyType>( null ); // For splay
private BinaryNode<AnyType> splay( AnyType x, BinaryNode<AnyType> t )
{
BinaryNode<AnyType> leftTreeMax, rightTreeMin;
header.left = header.right = nullNode;
leftTreeMax = rightTreeMin = header;
nullNode.element = x; // Guarantee a match
for( ; ; )
{
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
{
if( x.compareTo( t.left.element ) < 0 )
t = rotateWithLeftChild( t );
if( t.left == nullNode )
break;
// Link Right
rightTreeMin.left = t;
rightTreeMin = t;
t = t.left;
}
else if( compareResult > 0 )
{
if( x.compareTo( t.right.element ) > 0 )
t = rotateWithRightChild( t );
if( t.right == nullNode )
break;
// Link Left
leftTreeMax.right = t;
leftTreeMax = t;
t = t.right;
}
else
break;
}
leftTreeMax.right = t.left;
rightTreeMin.left = t.right;
t.left = header.right;
t.right = header.left;
return t;
}
private static <AnyType> BinaryNode<AnyType> rotateWithLeftChild( BinaryNode<AnyType> k2 )
{
BinaryNode<AnyType> k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
private static <AnyType> BinaryNode<AnyType> rotateWithRightChild( BinaryNode<AnyType> k1 )
{
BinaryNode<AnyType> k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
private static class BinaryNode<AnyType>
{
BinaryNode( AnyType theElement )
{
this( theElement, null, null );
}
BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
{
element = theElement;
left = lt;
right = rt;
}
AnyType element; // The data in the node
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
}
private BinaryNode<AnyType> root;
private BinaryNode<AnyType> nullNode;
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}
private void printTree( BinaryNode<AnyType> t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}
public static void main( String [ ] args ) throws Exception
{
SplayTree<Integer> tree = new SplayTree<Integer>();
for(int i = 0; i < 3; i ++)
tree.insert(i);
tree.printTree();
}
}