0

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(); 
    	
    }
}
2
Contributors
1
Reply
3
Views
7 Years
Discussion Span
Last Post by obscured47
0

I haven't checked your code properly but you're probably doing something wrong in the insert method and print() ends up in an infinite loop.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.