programming-examples/c++/Others/SplayTree.cpp - Implementation for top-down splay tree.cpp

SplayTree.cpp - Implementation for top-down splay tree
	
	#include <iostream.h>
        #include "SplayTree.h"

        /**
         * Construct the tree.
         */
        template <class Comparable>
        SplayTree<Comparable>::SplayTree( const Comparable & notFound )
          : ITEM_NOT_FOUND( notFound )
        {
            nullNode = new BinaryNode<Comparable>;
            nullNode->left = nullNode->right = nullNode;
            nullNode->element = notFound;
            root = nullNode;
        }

        /**
         * Copy constructor.
         */
        template <class Comparable>
        SplayTree<Comparable>::SplayTree( const SplayTree<Comparable> & rhs )
          : ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND )
        {
            nullNode = new BinaryNode<Comparable>;
            nullNode->left = nullNode->right = nullNode;
            nullNode->element = ITEM_NOT_FOUND;
            root = nullNode;
            *this = rhs;
        }

        /**
         * Destructor.
         */
        template <class Comparable>
        SplayTree<Comparable>::~SplayTree( )
        {
            makeEmpty( );
            delete nullNode;
        }

        /**
         * Insert x into the tree.
         */
        template <class Comparable>
        void SplayTree<Comparable>::insert( const Comparable & x )
        {
            static BinaryNode<Comparable> *newNode = NULL;

            if( newNode == NULL )
                newNode = new BinaryNode<Comparable>;
            newNode->element = x;

            if( root == nullNode )
            {
                newNode->left = newNode->right = nullNode;
                root = newNode;
            }
            else
            {
                splay( x, root );
                if( x < root->element )
                {
                    newNode->left = root->left;
                    newNode->right = root;
                    root->left = nullNode;
                    root = newNode;
                }
                else
                if( root->element < x )
                {
                    newNode->right = root->right;
                    newNode->left = root;
                    root->right = nullNode;
                    root = newNode;
                }
                else
                    return;
            }
            newNode = NULL;   // So next insert will call new
        }

        /**
         * Remove x from the tree.
         */
        template <class Comparable>
        void SplayTree<Comparable>::remove( const Comparable & x )
        {
            BinaryNode<Comparable> *newTree;

                // If x is found, it will be at the root
            splay( x, root );
            if( root->element != x )
                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;
                splay( x, newTree );
                newTree->right = root->right;
            }
            delete root;
            root = newTree;
        }

        /**
         * Find the smallest item in the tree.
         * Not the most efficient implementation (uses two passes), but has correct
         *     amortized behavior.
         * A good alternative is to first call Find with parameter
         *     smaller than any item in the tree, then call findMin.
         * Return the smallest item or ITEM_NOT_FOUND if empty.
         */
        template <class Comparable>
        const Comparable & SplayTree<Comparable>::findMin( )
        {
            if( isEmpty( ) )
                return ITEM_NOT_FOUND;

            BinaryNode<Comparable> *ptr = root;

            while( ptr->left != nullNode )
                ptr = ptr->left;

            splay( ptr->element, root );
            return ptr->element;
        }

        /**
         * Find the largest item in the tree.
         * Not the most efficient implementation (uses two passes), but has correct
         *     amortized behavior.
         * A good alternative is to first call Find with parameter
         *     larger than any item in the tree, then call findMax.
         * Return the largest item or ITEM_NOT_FOUND if empty.
         */
        template <class Comparable>
        const Comparable & SplayTree<Comparable>::findMax( )
        {
            if( isEmpty( ) )
                return ITEM_NOT_FOUND;

            BinaryNode<Comparable> *ptr = root;

            while( ptr->right != nullNode )
                ptr = ptr->right;

            splay( ptr->element, root );
            return ptr->element;
        }

        /**
         * Find item x in the tree.
         * Return the matching item or ITEM_NOT_FOUND if not found.
         */
        template <class Comparable>
        const Comparable & SplayTree<Comparable>::find( const Comparable & x )
        {
            if( isEmpty( ) )
                return ITEM_NOT_FOUND;
            splay( x, root );
            if( root->element != x )
                return ITEM_NOT_FOUND;

            return root->element;
        }

        /**
         * Make the tree logically empty.
         */
        template <class Comparable>
        void SplayTree<Comparable>::makeEmpty( )
        {
        /******************************
         * Comment this out, because it is prone to excessive
         * recursion on degenerate trees. Use alternate algorithm.
         
            reclaimMemory( root );
            root = nullNode;
         *******************************/
            findMax( );        // Splay max item to root
            while( !isEmpty( ) )
                remove( root->element );
        }

        /**
         * Test if the tree is logically empty.
         * @return true if empty, false otherwise.
         */
        template <class Comparable>
        bool SplayTree<Comparable>::isEmpty( ) const
        {
            return root == nullNode;
        }

        /**
         * Print the tree contents in sorted order.
         */
        template <class Comparable>
        void SplayTree<Comparable>::printTree( ) const
        {
            if( isEmpty( ) )
                cout << "Empty tree" << endl;
            else
                printTree( root );
        }

        /**
         * Deep copy.
         */
        template <class Comparable>
        const SplayTree<Comparable> &
        SplayTree<Comparable>::operator=( const SplayTree<Comparable> & rhs )
        {
            if( this != &rhs )
            {
                makeEmpty( );
                root = clone( rhs.root );
            }

            return *this;
        }

        /**
         * Internal method to perform a top-down splay.
         * The last accessed node becomes the new root.
         * This method may be overridden to use a different
         * splaying algorithm, however, the splay tree code
         * depends on the accessed item going to the root.
         * x is the target item to splay around.
         * t is the root of the subtree to splay.
         */
        template <class Comparable>
        void SplayTree<Comparable>::splay( const Comparable & x,
                                           BinaryNode<Comparable> * & t ) const
        {
            BinaryNode<Comparable> *leftTreeMax, *rightTreeMin;
            static BinaryNode<Comparable> header;

            header.left = header.right = nullNode;
            leftTreeMax = rightTreeMin = &header;

            nullNode->element = x;   // Guarantee a match

            for( ; ; )
                if( x < t->element )
                {
                    if( x < t->left->element )
                        rotateWithLeftChild( t );
                    if( t->left == nullNode )
                        break;
                    // Link Right
                    rightTreeMin->left = t;
                    rightTreeMin = t;
                    t = t->left;
                }
                else if( t->element < x )
                {
                    if( t->right->element < x )
                        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;
        }

        /**
         * Rotate binary tree node with left child.
         */
        template <class Comparable>
        void SplayTree<Comparable>::rotateWithLeftChild( BinaryNode<Comparable> * & k2 ) const
        {
            BinaryNode<Comparable> *k1 = k2->left;
            k2->left = k1->right;
            k1->right = k2;
            k2 = k1;
        }

        /**
         * Rotate binary tree node with right child.
         */
        template <class Comparable>
        void SplayTree<Comparable>::rotateWithRightChild( BinaryNode<Comparable> * & k1 ) const
        {
            BinaryNode<Comparable> *k2 = k1->right;
            k1->right = k2->left;
            k2->left = k1;
            k1 = k2;
        }

        /**
         * Internal method to print a subtree t in sorted order.
         * WARNING: This is prone to running out of stack space.
         */
        template <class Comparable>
        void SplayTree<Comparable>::printTree( BinaryNode<Comparable> *t ) const
        {
            if( t != t->left )
            {
                printTree( t->left );
                cout << t->element << endl;
                printTree( t->right );
            }
        }

        /**
         * Internal method to reclaim internal nodes in subtree t.
         * WARNING: This is prone to running out of stack space.
         */
        template <class Comparable>
        void SplayTree<Comparable>::reclaimMemory( BinaryNode<Comparable> * t ) const
        {
            if( t != t->left )
            {
                reclaimMemory( t->left );
                reclaimMemory( t->right );
                delete t;
            }
        }

        /**
         * Internal method to clone subtree.
         * WARNING: This is prone to running out of stack space.
         */
        template <class Comparable>
        BinaryNode<Comparable> *
        SplayTree<Comparable>::clone( BinaryNode<Comparable> * t ) const
        {
            if( t == t->left )  // Cannot test against nullNode!!!
                return nullNode;
            else
                return new BinaryNode<Comparable>( t->element, clone( t->left ), clone( t->right ) );
        }