Solved

Turning Binary Search Tree into Ternary Search Tree

Posted on 2003-10-28
3
697 Views
Last Modified: 2011-10-03
I need to turn the code for a Binary Search Treee into a Ternary search tree.  The file will not complile and states that the insert function does not accet four variables.  I also think that the atElement is wrong.  Can someone look this over an tell me what is wrong with it.  I don't know much about Ternary Search Trees and have been guessing at what needs to be modified.


        #ifndef _TERNARY_SEARCH_TREE_H_
        #define _TERNARY_SEARCH_TREE_H_

        #include "dsexceptions.h"
        #include <iostream>       // For NULL

          // Ternary node and forward declaration because g++ does
          // not understand nested classes.
        template <class Comparable>
        class TernarySearchTree;

        template <class Comparable>
        class TernaryNode
        {
//old Binary form
//          Comparable element;
//          TernaryNode *left;
//          TernaryNode *right;

            Comparable key1;
            Comparable key2;
            TernaryNode *left;
            TernaryNode *middle;
            TernaryNode *right;

//old Binary form
//            TernaryNode( const Comparable & theElement, TernaryNode *lt, TernaryNode *rt )
//              : element( theElement ), left( lt ), right( rt ) { }
//            friend class TernarySearchTree<Comparable>;

            TernaryNode( const Comparable & theKey1, const Comparable & theKey2,
                       TernaryNode *lt, TernaryNode *mid, TernaryNode *rt )
              : key1( theKey1 ), key2( theKey2), left( lt ), middle(mid), right( rt ) { }
            friend class TernarySearchTree<Comparable>;

        };


        // TernarySearchTree class
        //
        // CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
        //
        // ******************PUBLIC OPERATIONS*********************
        // void insert( x )       --> Insert x
        // void remove( x )       --> Remove x
        // Comparable find( x )   --> Return item that matches x
        // Comparable findMin( )  --> Return smallest item                        //remove
        // Comparable findMax( )  --> Return largest item                        //remove
        // boolean isEmpty( )     --> Return true if empty; else false
        // void makeEmpty( )      --> Remove all items
        // void printTree( )      --> Print tree in sorted order
        // int countNodes( )      --> Return number of nodes in tree  //added


        template <class Comparable>
        class TernarySearchTree
        {
          public:
            explicit TernarySearchTree( const Comparable & notFound );
            TernarySearchTree( const TernarySearchTree & rhs );
            ~TernarySearchTree( );

                  int GetLeftLinksFollowed() const;
                  int GetMiddleLinksFollowed() const;
                  int GetRightLinksFollowed() const;
                  double exp_path_len();

                  int card_of() const;
            const Comparable & findMin( ) const;
            const Comparable & findMax( ) const;
            const Comparable & find( const Comparable & x ) const;
            bool isEmpty( ) const;
            void printTree( ) const;
            int countNodes( ) const;

            void makeEmpty( );
            void insert( const Comparable & x );
            void remove( const Comparable & x );

            const TernarySearchTree & operator=( const TernarySearchTree & rhs );

          private:
            TernaryNode<Comparable> *root;
            const Comparable ITEM_NOT_FOUND;

                  mutable int num_nodes;
                  mutable int LeftLinksFollowed;
                  mutable int MiddleLinksFollowed;
                  mutable int RightLinksFollowed;
                  
                  const Comparable & elementAt( TernaryNode<Comparable> *t ) const;  
                  
            void insert( const Comparable & x, TernaryNode<Comparable> * & t ) const;
            void remove( const Comparable & x, TernaryNode<Comparable> * & t ) const;
            TernaryNode<Comparable> * findMin( TernaryNode<Comparable> *t ) const;
            TernaryNode<Comparable> * findMax( TernaryNode<Comparable> *t ) const;
            TernaryNode<Comparable> * find( const Comparable & x, TernaryNode<Comparable> *t ) const;
            void makeEmpty( TernaryNode<Comparable> * & t ) const;
            void printTree( TernaryNode<Comparable> *t ) const;
                  int countNodes( TernaryNode<Comparable> *t ) const;
            TernaryNode<Comparable> * clone( TernaryNode<Comparable> *t ) const;
        };


//Add your code for the TernarySearchTree class here


       /**
         * Implements an unbalanced Ternary search tree.
         * Note that all "matching" is based on the < method.
         */

        /**MMZ-OK
            * Construct the tree.
         */
        template <class Comparable>
        TernarySearchTree<Comparable>::TernarySearchTree( const Comparable & notFound ) :
          ITEM_NOT_FOUND( notFound ), root( NULL )
        {
                    LeftLinksFollowed = 0;
                    MiddleLinksFollowed = 0;
                    RightLinksFollowed = 0;
                    num_nodes = 0;
        }


        /**MMZ-OK
            * Copy constructor.
         */
        template <class Comparable>
        TernarySearchTree<Comparable>::
        TernarySearchTree( const TernarySearchTree<Comparable> & rhs ) :
          root( NULL ), ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND )
        {
            *this = rhs;
        }

        /**MMZ-OK
            * Destructor for the tree.
         */
        template <class Comparable>
        TernarySearchTree<Comparable>::~TernarySearchTree( )
        {
            makeEmpty( );
        }

        /**MMZ-OK
         * Insert x into the tree; duplicates are ignored.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::insert( const Comparable & x )
        {
            insert( x, root );
        }

        /**MMZ-OK
         * Remove x from the tree. Nothing is done if x is not found.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::remove( const Comparable & x )
        {
            remove( x, root );
        }

        /**MMZ-OK
         * Returns the number of left links followed so far in the tree.
         */
        template <class Comparable>
        int TernarySearchTree<Comparable>::GetLeftLinksFollowed( ) const
        {
            return LeftLinksFollowed;
        }

        /**MMZ-OK
         * Returns the number of middle links followed so far in the tree.
         */
        template <class Comparable>
        int TernarySearchTree<Comparable>::GetMiddleLinksFollowed( ) const
        {
            return MiddleLinksFollowed;
        }

        /**MMZ-OK
         * Returns the number of right links followed so far in the tree.
         */
        template <class Comparable>
        int TernarySearchTree<Comparable>::GetRightLinksFollowed( ) const
        {
            return RightLinksFollowed;
        }

        /**MMZ-OK
            * Returns the cardinality (number of nodes) in the tree.
            */
        template <class Comparable>
                  int TernarySearchTree<Comparable>::card_of( ) const
        {
            return num_nodes;
        }
            
            template <class Comparable>
                  double TernarySearchTree<Comparable>::exp_path_len( )
                  /*
                  **  Calculate the expected path length of the tree
                  **  This is the public version, without a parameter.
                  **  NOTE that it recursively invokes int_path_length()
                  */
        {
                  // YOUR CODE HERE
                  return -99.0;  // stub, remove after writing your code
        }
            
        /**MMZ-OK
            * Find the smallest item in the tree.
            * Return smallest item or ITEM_NOT_FOUND if empty.
            */
        template <class Comparable>
        const Comparable & TernarySearchTree<Comparable>::findMin( ) const
        {
            return elementAt( findMin( root ) );
        }

        /**MMZ-OK
         * Find the largest item in the tree.
         * Return the largest item of ITEM_NOT_FOUND if empty.
         */
        template <class Comparable>
        const Comparable & TernarySearchTree<Comparable>::findMax( ) const
        {
            return elementAt( findMax( root ) );
        }

        /**MMZ-OK
         * Find item x in the tree.
         * Return the matching item or ITEM_NOT_FOUND if not found.
         */
        template <class Comparable>
        const Comparable & TernarySearchTree<Comparable>::
                                 find( const Comparable & x ) const
        {
            return elementAt( find( x, root ) );
        }

        /**MMZ-OK
         * Make the tree logically empty.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::makeEmpty( )
        {
            makeEmpty( root );
        }

        /**MMZ-OK
         * Test if the tree is logically empty.
         * Return true if empty, false otherwise.
         */
        template <class Comparable>
        bool TernarySearchTree<Comparable>::isEmpty( ) const
        {
            return root == NULL;
        }

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

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


/////////////////////////////////////////
        /**MMZ-??????
         * Internal method to get element field in node t.
         * Return the element field or ITEM_NOT_FOUND if t is NULL.
         */
        template <class Comparable>
        const Comparable & TernarySearchTree<Comparable>::
        elementAt( TernaryNode<Comparable> *t ) const
        {
/*                  orginal code
            return t == NULL ? ITEM_NOT_FOUND : t->element; */
              return t == NULL ? ITEM_NOT_FOUND : t->key1 ? t->key2;

//Maybe something like this????
//          return ITEM_NOT_FOUND : t->key1;  ///?????
//          return ITEM_NOT_FOUND : t->key2;  ///?????

        }

        /**MMZ-?????
            * Internal method to insert into a subtree.
            * x is the item to insert.
            * t is the node that roots the tree.
            * Set the new root.
            */
        template <class Comparable>
                  void TernarySearchTree<Comparable>::
                  insert( const Comparable & x, TernaryNode<Comparable> * & t ) const
        {
            if( t == NULL )
                  {
/*                  orginal code
                t = new BinaryNode<Comparable>( x, NULL, NULL ); */
                t = new TernaryNode<Comparable>( x, NULL, NULL, NULL ); //?????????
                  }
            else if( x < t->key1 )
                  {
                insert( x, t->left );
                  }
            else if((x > t->key1) && (x < t->key2))
                  {
                insert( x, t->middle );
                  }
                  else if( x > t->key2 )
                  {
                insert( x, t->right );
                  }
            else; // Duplicate; do nothing
             
        }

       /**
         * Internal method to remove from a subtree.
         * x is the item to remove.
         * t is the node that roots the tree.
         * Set the new root.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::
        remove( const Comparable & x, TernaryNode<Comparable> * & t ) const
        {
            if( t == NULL )
                return;   // Item not found; do nothing
            if( x < t->key1 )
                remove( x, t->left );
            if((x > t->key1) && (x < t->key2))
                remove( x, t->middle );
            else if( x > t->key2 )
                remove( x, t->right );
            else if( t->left !=NULL && t->middle !=NULL && t->right !=NULL ) // Three children
            {
                t->key2 = findMin( t->right )->key2;
                remove( t->key2, t->right );
            }
            else
            {
                TernaryNode<Comparable> *oldNode = t; ///????????????
                t = ( t->left != NULL ) ? t->left : t->right;
                delete oldNode;
            }
        }


        /**MMZ-OK because smallest is still in left tree
         * Internal method to find the smallest item in a subtree t.
         * Return node containing the smallest item.
         */
        template <class Comparable>
        TernaryNode<Comparable> *
        TernarySearchTree<Comparable>::findMin( TernaryNode<Comparable> *t ) const
        {
            if( t == NULL )
                return NULL;
            if( t->left == NULL )
                return t;
            return findMin( t->left );
        }

        /**MMZ-OK because largest is still in right tree
         * Internal method to find the largest item in a subtree t.
         * Return node containing the largest item.
         */
        template <class Comparable>
        TernaryNode<Comparable> *
        TernarySearchTree<Comparable>::findMax( TernaryNode<Comparable> *t ) const
        {
            if( t != NULL )
                while( t->right != NULL )
                    t = t->right;
            return t;
        }

        /**MMZ-OK
         * Internal method to find an item in a subtree.
         * x is item to search for.
         * t is the node that roots the tree.
         * Return node containing the matched item.
         */
        template <class Comparable>
        TernaryNode<Comparable> *
        TernarySearchTree<Comparable>::
        find( const Comparable & x, TernaryNode<Comparable> *t ) const
        {
            if( t == NULL )
                return NULL;
            else if( x < t->key1 )
                  {
                return find( x, t->left );
            }
                  else if((x > t->key1) && (x < t->key2))
                  {
                        return find( x, t->middle );
            }
                  else if( t->element < x )
                  {
                        return find( x, t->right );
            }

                  else
                return t;    // Match
        }


        /**MMZ-OK
         * Internal method to make subtree empty.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::
        makeEmpty( TernaryNode<Comparable> * & t ) const
        {
            if( t != NULL )
            {
                makeEmpty( t->left );
                makeEmpty( t->middle );
                makeEmpty( t->right );
                delete t;
            }
            t = NULL;
        }

        /**MMZ-OK
         * Internal method to print a subtree rooted at t in sorted order.
         */
        template <class Comparable>
        void TernarySearchTree<Comparable>::printTree( TernaryNode<Comparable> *t ) const
        {
            if( t != NULL )
            {
                printTree( t->left );
                        cout << t->key1 << endl;
                printTree( t->middle );
                        cout << t->key2 << endl;
                printTree( t->right );
            }
        }

        /**MMZ-OK
         * Internal method to clone subtree.
         */
        template <class Comparable>
        TernaryNode<Comparable> *
        TernarySearchTree<Comparable>::clone( TernaryNode<Comparable> * t ) const
        {
            if( t == NULL )
                return NULL;
            else
                return new TernaryNode<Comparable>( t->key1, t->key2, clone( t->left ), clone( t->middle ), clone( t->right ) );
        }

       /**MMZ-OK
         * Return the #nodes in the tree.
         */
        template <class Comparable>
        int TernarySearchTree<Comparable>::countNodes( ) const
        {
            if( isEmpty( ) )
                return 0 ;
            else
                return countNodes( root );
        }

        /**MMZ-OK
         * Internal method to count #nodes in tree rooted at t.
         */
        template <class Comparable>
        int TernarySearchTree<Comparable>::countNodes( TernaryNode<Comparable> *t ) const
        {
            if( t == NULL )
            return 0 ;
          return countNodes(t->left) + countNodes(t->middle) + countNodes(t->right) + 1 ;
        }

        #endif
0
Comment
Question by:byonmarz
  • 2
3 Comments
 
LVL 7

Expert Comment

by:burcarpat
ID: 9635499
copy'n paste the error message and the compiler you're using.  that'll be helpful

-- ba
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 9635529
I don't know anything of ternary trees either.

But the compile error is because of this

        t = new TernaryNode<Comparable>( x, NULL, NULL, NULL ); //?????????

The constructor of TernaryNode wants two keys and you provide only one (x).

I suppose that such a tree looks like this (with letters as keys and numbers as pointers)

Level              
1                                       [1]  2   'G'  3  'M'  4
2                   [2] 5   'B'  6  'F'  7     [3]  8  'I'  9 'L' 10    [4]  11 'S' 12 'V' 13
3 ....

Then you see, that initially when inserting the first key 'G'  you have a problem by not having a second key for the first entry. Generally, when adding a new entry, you always have only one key. You can solve the problem by using an empty key as placeholder, i. e. all new entries are binary entries first, having one key and two null pointers. Because it is a template class you would need an instance of that empty key provided by the constructor of the tree, similar to that of the notFound key. Or you take the notFound key as placeholder:

                  t = new TernaryNode<Comparable>( x, notFound, NULL, NULL, NULL );

But then, you got some new problems, because you have to handle the case of having notFound as key2 at any place where key2 is used.

I don't believe a ternary tree is a big advantage.

Regards, Alex

Regards, Alex
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 500 total points
ID: 9635710
I tried to run this code and it works in my BOOL CTestDlgApp::InitInstance()


    ....

    CString strNotFound = "notFound";
    TernarySearchTree<CString> testTree(strNotFound);

    testTree.insert("Anton");
    testTree.insert("Xelda");
    testTree.insert("Berta");
    testTree.insert("Gabriel");
    testTree.insert("Lucy");
    testTree.insert("Henry");

    ....


I did change TernaryNode::insert(..)

template <class Comparable>
       void TernarySearchTree<Comparable>::
       insert( const Comparable & x, TernaryNode<Comparable> * & t ) const
{
    if( t == NULL )
       {
/*               orginal code
        t = new BinaryNode<Comparable>( x, NULL, NULL ); */
        t = new TernaryNode<Comparable>( x, ITEM_NOT_FOUND, NULL, NULL, NULL ); //?????????
       }
    else if( (x < t->key1)  && (t->key2 == ITEM_NOT_FOUND) )
       {
          t->key2   = t->key1;
          t->key1   = x;
          t->right  = t->middle;
          t->middle = t->left;
          t->left   = NULL;
       }
    else if( x < t->key1 )
       {
        insert( x, t->left );
       }
    else if((x > t->key1) && (t->key2 == ITEM_NOT_FOUND))
       {
          t->key2 = x;
       }
    else if((x > t->key1) && (t->key2 == ITEM_NOT_FOUND || x < t->key2))
       {
        insert( x, t->middle );
       }
       else if( x > t->key2 )
       {
        insert( x, t->right );
       }
    else; // Duplicate; do nothing
     
}

This works, but the resulting tree was very very unbalanced.

                                         [ANTON   XELDA]

                                         [BERTA  GABRIEL]              

                                                                                [HENRY LUCY]

Regards, Alex

0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now