Go4Expert

Go4Expert (http://www.go4expert.com/)
-   Java (http://www.go4expert.com/forums/java/)
-   -   Splay Tree Problem (http://www.go4expert.com/forums/splay-tree-problem-t21354/)

moonieman 14Mar2010 11:33

Splay Tree Problem
 
Hello,

I keep getting a stack over flow problem on the print function. This function worked fine on other trees but not on the splay tree. After inserting the items into the tree I wanted the print function to display them.

The error message looks like this :
Exception in thread "main" java.lang.StackOverflowError
at v1.SplayTree.printTree(SplayTree.java:290)


Please help?

Thank you.



Code:

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; 
   

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

        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;       
        BinaryNode<AnyType> left; 
        BinaryNode<AnyType> right; 
    }

    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 < 10; i ++)
               
                tree.insert(i);
          tree.printTree();
       
    }
}



All times are GMT +5.5. The time now is 08:43.