compile errors

Question

deerowbear 0 Newbie Poster

15 Years Ago

I am getting these errors when compiling, and I am not sure why. Any help is much appreciated.

Thanks daniel

/////errors
77 C:\Users\dwilmes\Desktop\project3\main.cpp expected constructor, destructor, or type conversion before '<' token
77 C:\Users\dwilmes\Desktop\project3\main.cpp expected `;' before '<' token
83 C:\Users\dwilmes\Desktop\project3\main.cpp expected constructor, destructor, or type conversion before '<' token
83 C:\Users\dwilmes\Desktop\project3\main.cpp expected `;' before '<' token
91 C:\Users\dwilmes\Desktop\project3\main.cpp expected init-declarator before '<' token
91 C:\Users\dwilmes\Desktop\project3\main.cpp expected `;' before '<' token
107 C:\Users\dwilmes\Desktop\project3\main.cpp expected init-declarator before '<' token
107 C:\Users\dwilmes\Desktop\project3\main.cpp expected `;' before '<' token
125 C:\Users\dwilmes\Desktop\project3\main.cpp expected init-declarator before '<' token
125 C:\Users\dwilmes\Desktop\project3\main.cpp expected `;' before '<' token
/////////end errors

#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <string>
#include <cctype>
#include <sstream>
//#include "comparable.h"

using namespace std;
//
enum cmp_t
{
 MIN_CMP = -1,
 EQ_CMP = 0,
 MAX_CMP = 1
};

template <class KeyType>
class Comparable
{
 private:
         KeyType myKey;
         
 public:
    Comparable(KeyType key) : myKey(key){};
    cmp_t Compare(KeyType Key) const
    {
     return(Key == myKey) ? EQ_CMP :((Key < myKey) ? MIN_CMP : MAX_CMP);     
    }
    KeyType Key() const { return myKey; }
    void Print() const
    {
     cout << myKey;     
    }
};
//
inline static int 
MIN (int a, int b) 
{
	return (a < b) ? a:b;
};

inline static int
MAX (int a, int b)
{
	return (a > b) ? a:b; 
};

enum balance_t
{
	LEFT_HEAVY = -1,
	BALANCED = 0,
	RIGHT_HEAVY = 1
};

enum height_effect_t
{
	HEIGHT_UNCHANGED = 0,
	HEIGHT_CHANGED = 0
};

inline static int
LEFT_INBALANCE(short bal)
{
	return (bal < LEFT_HEAVY);
};

inline static int
RIGHT_INBALANCE(short bal)
{
	return(bal > RIGHT_HEAVY);
}

template <class KeyType>
AVLNode<KeyType>::AVLNode(comparable <KeyType> * item):myData(item), myBal(0)
{
	Reset();
}

template <class KeyType>
AVLNode<KeyType>~AVLNode(void)
{
	if(myTree) delete mySubTree;
	if(myTree)delete mySubTree;
};

template<class KeyType>
int
AVLNode <KeyType>::RotateOnce(AVLNode <KeyType>  * & root, dir_t dir)
{ 
	dir_t otherdir = oposite(dir);
	AVLNode<KeyType> * oldRoot = root;
	int heightChange = (root -> mySubTree[otherdir]-> myBal == 0);
	?HEIGHT_NOCHANGE;
	:HEIGHT_CHANGE;
	root = oldRoot -> mySubTree[otherdir];
	oldRoot -> mySubTree[otherdir] = root -> mySubTree[dir];
	root -> mySubTree[dir] = oldRoot;
	oldRoot -> myBal = -((dir == LEFT))? --(root -> myBal): ++(root -> myBal));
	return heightChange;
};

template<class KeyType>
int
AVLNode <KeyType>::RotateTwice(AVLNode <KeyType>  * & root, dir_t dir)
{
	dir_t otherdir = opposite(dir);
	AVLNode <KeyType> * oldRoot = root;
	AVLNode <KeyType> * oldOtherDirSubTree = root -> mySubTree[otherdir];
	root = oldRoot -> mySubTree(otherdir) -> mySubTree[dir];
	oldRoot -> mySubTree[otherdir] = root -> mySubTee[dir];
	root -> mySubtee[dir] = oldRoot;
	oldOtherDirSubTree -> mySbutree[dir] = root -> mySubTee[otherdir];
	root -> mySubTree[otherdir] = oldOtherDirSubTree;
	root -> mySubTree  -> myBal = -MAX(root -> myBal, 0);
	root -> mySubTree  -> myBal = -MIN(root -> myBal, 0);
	root -> myBal = 0;
	return HEIGHT_CHANGE;
};

template<class KeyType>
int
AVLNode <KeyType>::ReBalance(AVLNode <KeyType>  * & root)
{
	int heightChange = HEIGHT_NOCHANGE;
	if(LEFT_INBALANCE (root -> myBal))
	{
		if( root -> mySubTree -> myBal == RIGHT_HEAVY )
		{
		//RL
		heightChange = RotateTwice (root, RIGHT);
		}
		else
		{
			heightChange =  RotateOnce(root, RIGHT);
		}
	else if (RIGHT_INBALANCE(root -> myBal))
	{
		if(root -> mySubTree-> myBal == LEFT_HEAVY)
		{
			//left right rotation
			heightCHange = RotateTwince(root, LEFT);
		}
		else
		{
			heightChange = RotateOnce(root, LEFT);
		}
	}
	return heightChange;
};

template <class KeyType>
cmp_t AVLNode <KeyType>::Compare(KeyType Key, cmp_t cmp) const
{
	switch(cmp)
	{
	case EQ_CMP:
		return mydate -> compare(Key);
	Case MIN_cmp:
		return (mySubTree)==NULL ? EQ_CMP:MIN_CMP
	case MAX_cmp:
		return(mySubTree==NULL) ? EQ_CMP:MAX_cmp
	}
};

template <class KeyType>
comparable <KeyType> * AVLNode <KeyType>::Search(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp)
{
 cmp_t result;
 while(root && (results = root -> comare(Key, cmp))
 {
  root = root -> mySubTree[(result < 0) ? LEFT : RIGHT];           
 }
};

template <class KeyType>
comparable <KeyType> * AVLNode <KeyType>::Delete(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp)
{
 cmp_t result;
 while(root && (results = root -> comare(Key, cmp))
 {
  root = root -> mySubTree[(result < 0) ? LEFT : RIGHT];           
 }
};

template <class KeyType>
comparable <KeyType> * AVLNode <KeyType>::Insert(comparable<KeyType> *item, AVLNode <KeyType> * & root)
{
	int change;
	return Insert(item, root, change)
};

template <class KeyType>
comparabe <KeyType> AVLNode<KeyType>::Insert(comparable<KeyType> *item,
AVLNode<KeyType> *&root, int &change)
{
	if(root == NULL)
	{
		root = new AVLNode<KeyType>(item),
		Change = HEIGHT_CHANGE,
		return NULL
	}
	Comparable<KeyType> * found = NULL
	int increase = 0;
	cmt_t result = root -> compare (item -> Key())
	dir_t dir = (result == MIN_CMP) ? LEFT:RIGHT
	if(result != EQ_CMP)
	{
		found = Insert(item, root -> mySubTree[dir], change)
		if(found) reurn found;
		increase = result *change
	}
	else
	{
		increase = HEIHT_NOCHANGE
		return root -> myData;
		root -> myBal += increase;
		change = (increase && root -> myBal)?(1-Rebaance(root)): HEIGHT_NOCHANGE;
		return NULL;
	}
};

enum dir_t
{
	LEFT = 0;
	RIGHT = 1;
};

//AVL NODE
template<class KeyType>
class AVLNode
{
public:
	enum {MAX_SUBTREE = 2;}
	static dir_t opposite(dir_t dir)
	{
		return dir_t( 1 - int( dir ) )
	}
	AVLNode(comparable <KeyType> * item = null)
	virtual ~AVLNode(void);
	comparable <KeyType> * Data() const {return myDate};
	KeyType Key() const
	{
		return myData -> Key();
	}
	//balance vector
	static Bal ( void ) const
	{
		return myBal;
	}
	AVLNode * SubTree(dir_t dir) const { return mySubTree[dir]; }
	//searching
	static comparable <KeyType> *search
	(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp = EQ_CMP);
	//insert
	static comparable <KeyType>
	*Insert(comparable <KeyType> *item, AVLNode <KeyType> *&root);
	static comparable <KeyType> *
	Delete (KeyType Key, AVLNode <KeyType> *&root, cmp_t cmp = EQ_CMP)
	{
		int Height() const;
		int check() const;
	}
Private:
	comparable <KeyType> *myDate;
	AVLNode <KeyType> *mySubTree[MAX_SUBTREE];
	short myBal;
	void Reset(void)
	{
		myBal = 0;
		mySubTree = mySubTree = NULL
	}	
	static comparable<KeyType> *
	insert (comparable<KeyType> * item, AVLNode<KeyType> * & root, int & change);
	static comparable<KeyType>
	Delete(KeyType Key, AVLNode<KeyType> *&root, int &change, cmp_t cmp = EQ_CMP);
	static int RotateOnce(AVLNode<KeyType> *&root, dir_t dir);
	static int rotateTwice(AVLNode<KeyType> *&root, dir_t dir);
	static int ReBalance(AVLNode<KeyType> *&root);
	cmp_t compare(KeyType> Key, cmp_t, cmp = EQ_CMP) const;
Private:
	AVLNode(const AVLNode<KeyType> &);
	AVLNode & operator = (const AVLNode<KeyType> &);
};

template <class KeyType>	
class AVLTree
{
	private:
		AVLTree(const AVLTree<KeyType> &)
		AVLTree & operator = (const AVLTree<KeyType> &);
		AVLNode<KeyType> * myRoot;
	Public:
		AVLNode():myRoot(NULL){}
		~AVLNode()
		{
			if(myRoot)
			delete myRoot;
		}
		comparable<kyeType> *search(KeyType Key, cmp_t cmp=EQ_CMP
		{
			return AVLNode<KeyType>::search(Key, myRoot, cmp);
		}
		comparable<KeyType>::*insert(comparable<KeyType> *item)
		{
			return AVLNode<KeyType>::insert(item, myRoot);
		}
		comparable<KeyType> *Delete(KeyType Key, cmp_t, cmp = EQ_CMP)
		{
			return AVLNode<KeyType>::Delete(Key, myRoot, cmp);
		}
		void DumpTree() const;
		int isEmpty()
		{
			return myRoot == NULL;
		}
};

template <class KeyType>
Comparable<KeyType> *
AVLNode<KeyType>::Search(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp)
{
   cmp_t result;
   while (root  &&  (result = root->Compare(Key, cmp))) {
      root = root->mySubTree[(result < 0) ? LEFT : RIGHT];
   }
   return  (root) ? root->myData : NULL;
};


template <class KeyType>
Comparable<KeyType> *
AVLNode<KeyType>::Delete(KeyType Key, AVLNode<KeyType> * & root, cmp_t cmp)
{
   int  change;
   return  Delete(Key, root, change, cmp);
};


template <class KeyType>
Comparable<KeyType> *
AVLNode<KeyType>::Delete(KeyType Key, AVLNode<KeyType> * & root, int & change, cmp_t cmp)
{
      // See if the tree is empty
   if (root == NULL) {
         // Key not found
      change = HEIGHT_NOCHANGE;
      return  NULL;
   }

      // Initialize
   Comparable<KeyType> * found = NULL;
   int  decrease = 0;
      // Compare items and determine which direction to search
   cmp_t  result = root->Compare(Key, cmp);
   dir_t  dir = (result == MIN_CMP) ? LEFT : RIGHT;
   if (result != EQ_CMP) {
         // Delete from "dir" subtree 
      found = Delete(Key, root->mySubTree[dir], change, cmp);
      if (! found)  return  found;   // not found - can't delete
      decrease = result * change;    // set balance factor decrement
   } else  {   // Found Key at this node
      found = root->myData;  // set return value

      // ---------------------------------------------------------------------
      // At this point we know "result" is zero and "root" points to
      // the node that we need to delete.  There are three cases:
      //
      //    1) The node is a leaf.  Remove it and return.
      //
      //    2) The node is a branch (has only 1 child). Make "root"
      //       (the pointer to this node) point to the child.
      //
      //    3) The node has two children. We swap items with the successor
      //       of "root" (the smallest item in its right subtree) and delete
      //       the successor from the right subtree of "root".  The
      //       identifier "decrease" should be reset if the subtree height
      //       decreased due to the deletion of the successor of "root".
      // ---------------------------------------------------------------------
      if ((root->mySubTree == NULL) &&
          (root->mySubTree == NULL)) {
             // We have a leaf -- remove it
         delete  root;
         root = NULL;
         change = HEIGHT_CHANGE;    // height changed from 1 to 0
         return  found;
      } else if ((root->mySubTree == NULL) ||
                 (root->mySubTree == NULL)) {
            // We have one child -- only child becomes new root 
         AVLNode<KeyType> * toDelete = root;
         root = root->mySubTree[(root->mySubTree) ? RIGHT : LEFT];
         change = HEIGHT_CHANGE;    // We just shortened the subtree
            // Null-out the subtree pointers so we dont recursively delete
         toDelete->mySubTree = toDelete->mySubTree = NULL;
         delete  toDelete;
         return  found;
      } else {
            // We have two children -- find successor and replace our current
            // data item with that of the successor
         root->myData = Delete(Key, root->mySubTree,
                               decrease, MIN_CMP);
      }
   }
   root->myBal -= decrease;       // update balance factor 
   // ------------------------------------------------------------------------
   // Rebalance if necessary -- the height of current tree changes if one
   // of two things happens: (1) a rotation was performed which changed
   // the height of the subtree (2) the subtree height decreased and now
   // matches the height of its other subtree (so the current tree now
   // has a zero balance when it previously did not).
   // ------------------------------------------------------------------------
   //change = (decrease) ? ((root->myBal) ? balance(root) : HEIGHT_CHANGE)
   //                    : HEIGHT_NOCHANGE ;
   if (decrease) {
      if (root -> myBal) {
         change = ReBalance(root);  // rebalance and see if height changed
      } else {
         change = HEIGHT_CHANGE;   // balanced because subtree decreased
      }
   } else {
      change = HEIGHT_NOCHANGE;
   }
   return  found;
}

static inline void
Indent( int len) {
   for (int i = 0; i < len; i++) {
      cout << ' ';
   }
}

enum TraversalOrder { LTREE, Key, RTREE };

template <class KeyType>
static void
Dump(
     TraversalOrder order,
     const AVLNode<KeyType> * node,
     int level=0)
{
    unsigned  len = (level * 5) + 1;
    if ((order == LTREE) && (node->Subtree(LEFT) == NULL)) {
       Indent( len); 
       cout << "     **NULL**" << endl;
    }
    if (order == Key) {
       Indent( len); 
       cout << node->Key() << ":" << node->Bal() << endl;
    }
    if ((order == RTREE) && (node->Subtree(RIGHT) == NULL)) {
       Indent( len); 
       cout << "     **NULL**" << endl;
    }
}

template <class KeyType>
static void
Dump(const AVLNode<KeyType> * node, int level=0)
{
   if (node == NULL) {
      cout << "***EMPTY TREE***" << endl;
   } else {
      Dump( RTREE, node, level);
      if (node->Subtree(RIGHT)  !=  NULL) {
         Dump( node->Subtree(RIGHT), level+1);
      }
      Dump( Key, node, level);
      if (node->Subtree(LEFT)  !=  NULL) {
         Dump( node->Subtree(LEFT), level+1);
      }
      Dump(LTREE, node, level);
   }// if non-empty tree
}

template <class KeyType>
void
AvlTree<KeyType>::DumpTree() const {
   Dump(myRoot);
}

// Sample main code

main()
{
    char stop;
    AvlTree<long> tree;
    Comparable<long> * found = NULL;
    long inputValue;
	Comparable<long> *myarray[25];

	
	int numVoters;
	ifstream inputFile;

	inputFile.open("testvals.txt");
	if (!inputFile)
		cout<<"Error on opening file"<<endl;
	numVoters = 0;
	while (!inputFile.eof()&& numVoters < 25)
	{
        inputFile>>inputValue;
		myarray[numVoters] = new Comparable<long>(inputValue);
		numVoters++;
	}
	cout<<" Initial Input"<<endl;
    for (int i = 0; i<numVoters; i++)
      {
             cout<<myarray[i]->Key()<<endl;
      }
     int  i;
    for (i = 0 ; i < numVoters ; i++)  {
       cout << "+++ inserting Key #" << i+1 << ": " << myarray[i]->Key() << endl;
       found = tree.Insert(myarray[i]);
       if (found) {
          cout << "\t(already in tree)\n";
       }
      }
    tree.DumpTree();
    cin >> stop;
        system("PAUSE");
    return EXIT_SUCCESS; 
}

c++

4 Contributors
8 Replies
99 Views
1 Day Discussion Span
Latest Post 15 Years Ago Latest Post by Ancient Dragon

All 8 Replies

Ancient Dragon 5,243 Achieved Level 70

15 Years Ago

The very first error message should have told you that AVLNode is undefined

daviddoria 334 Posting Virtuoso

15 Years Ago

Yea, but it looks like you're using it on line 77 and defining it on line 241 - you need to define it before you use it!

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

deerowbear 0 Newbie Poster · Answer 1 · 2009-03-01T18:31:06+00:00

I thought since in line 241-242 I declared class AVLNode
defining these two functions:

AVLNode(comparable <KeyType> * item = null)	
virtual ~AVLNode(void);

Isn't that declaring an AVLNode?

Thanks Daniel

deerowbear 0 Newbie Poster · Answer 2 · 2009-03-01T23:14:40+00:00

Yeah, I changed the where I declare the class and implement the functions. However, I am getting a lot of errors now.

#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <string>
#include <cctype>
#include <sstream>
//#include "Comparable.h"

using namespace std;
//
enum cmp_t
{
 MIN_CMP = -1,
 EQ_CMP = 0,
 MAX_CMP = 1
};

template <class KeyType>
class Comparable
{
 private:
         KeyType myKey;
         
 public:
    Comparable(KeyType key) : myKey(key){};
    cmp_t Compare(KeyType Key) const
    {
     return(Key == myKey) ? EQ_CMP :((Key < myKey) ? MIN_CMP : MAX_CMP);     
    }
    KeyType Key() const { return myKey; }
    void Print() const
    {
     cout << myKey;     
    }
};
//
inline static int 
MIN (int a, int b) 
{
	return (a < b) ? a:b;
};

inline static int
MAX (int a, int b)
{
	return (a > b) ? a:b; 
};

enum balance_t
{
	LEFT_HEAVY = -1,
	BALANCED = 0,
	RIGHT_HEAVY = 1
};

enum height_effect_t
{
	HEIGHT_UNCHANGED = 0,
	HEIGHT_CHANGED = 0
};

inline static int
LEFT_INBALANCE(short bal)
{
	return (bal < LEFT_HEAVY);
};

inline static int
RIGHT_INBALANCE(short bal)
{
	return( bal > RIGHT_HEAVY );
}

enum dir_t
{
	LEFT = 0,
	RIGHT = 1
};
//AVL NODE
template<class KeyType>
class AVLNode
{
public:
	enum {MAX_SUBTREE = 2}
	static dir_t Opposite(dir_t dir)
	{
		return dir_t( 1 - int(dir))
	};
	AVLNode(Comparable <KeyType> * item = null);
	virtual ~AVLNode(void){};
	Comparable <KeyType> * Data() const {return myDate;};
	KeyType Key() const
	{
		return myData -> Key();
	};
	//balance vector
	static Bal ( void ) const
	{
		return myBal;
	};
	AVLNode * SubTree(dir_t dir) const { return mySubTree[dir]; }
	//searching
	static Comparable <KeyType> *search	(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp = EQ_CMP);
	//insert
	static Comparable <KeyType>	*Insert(Comparable <KeyType> *item, AVLNode <KeyType> *&root);
	static Comparable <KeyType> *Delete (KeyType Key, AVLNode <KeyType> *&root, cmp_t cmp = EQ_CMP)
	{
		int Height() const;
		int check() const;
	}
Private:
	Comparable <KeyType> * myDate;
	AVLNode <KeyType> * mySubTree[MAX_SUBTREE];
	short myBal;
	void Reset(void)
	{
		myBal = 0;
		mySubTree = mySubTree = NULL;
	}	
	static Comparable <KeyType> * insert (Comparable<KeyType> * item, AVLNode<KeyType> * & root, int & change);
	static Comparable<KeyType> Delete(KeyType Key, AVLNode<KeyType> *&root, int &change, cmp_t cmp = EQ_CMP);
	static int RotateOnce(AVLNode<KeyType> *&root, dir_t dir);
	static int rotateTwice(AVLNode<KeyType> *&root, dir_t dir);
	static int ReBalance(AVLNode<KeyType> *&root);
	cmp_t Comparable <KeyType> Key, cmp_t, cmp = EQ_CMP) const;
Private:
	AVLNode(const AVLNode<KeyType> &);
	AVLNode & operator = (const AVLNode<KeyType> &);
};

template <class KeyType>	
class AvlTree
{
	private:
		AvlTree(const AvlTree<KeyType> &);
		AvlTree & operator = (const AvlTree<KeyType> &);
		AVLNode<KeyType> * myRoot;
	Public:
		AVLNode():myRoot(NULL){};
		~AVLNode()
		{
			if(myRoot)
			delete myRoot;
		}
		Comparable<kyeType> *search(KeyType Key, cmp_t cmp=EQ_CMP
		{
			return AVLNode<KeyType>::search(Key, myRoot, cmp);
		}
		Comparable<KeyType>::*insert(Comparable<KeyType> *item)
		{
			return AVLNode<KeyType>::insert(item, myRoot);
		}
		Comparable<KeyType> *Delete(KeyType Key, cmp_t, cmp = EQ_CMP)
		{
			return AVLNode<KeyType>::Delete(Key, myRoot, cmp);
		}
		void DumpTree() const;
		int isEmpty()
		{
			return myRoot == NULL;
		}
};

template <class KeyType>
AVLNode<KeyType>::AVLNode(Comparable <KeyType> * item) : myData(item), myBal(0)
{
	Reset();
}

template <class KeyType>
AVLNode<KeyType>~AVLNode(void)
{
	if(myTree) delete mySubTree;
	if(myTree)delete mySubTree;
};

template<class KeyType>
int
AVLNode <KeyType>::RotateOnce(AVLNode <KeyType>  * & root, dir_t dir)
{ 
	dir_t otherdir = oposite(dir);
	AVLNode<KeyType> * oldRoot = root;
	int heightChange = (root -> mySubTree[otherdir]-> myBal == 0);
	?HEIGHT_NOCHANGE;
	:HEIGHT_CHANGE;
	root = oldRoot -> mySubTree[otherdir];
	oldRoot -> mySubTree[otherdir] = root -> mySubTree[dir];
	root -> mySubTree[dir] = oldRoot;
	oldRoot -> myBal = -((dir == LEFT))? --(root -> myBal): ++(root -> myBal));
	return heightChange;
};

template<class KeyType>
int
AVLNode <KeyType>::RotateTwice(AVLNode <KeyType>  * & root, dir_t dir)
{
	dir_t otherdir = Opposite(dir);
	AVLNode <KeyType> * oldRoot = root;
	AVLNode <KeyType> * oldOtherDirSubTree = root -> mySubTree[otherdir];
	root = oldRoot -> mySubTree(otherdir) -> mySubTree[dir];
	oldRoot -> mySubTree[otherdir] = root -> mySubTee[dir];
	root -> mySubtee[dir] = oldRoot;
	oldOtherDirSubTree -> mySbutree[dir] = root -> mySubTee[otherdir];
	root -> mySubTree[otherdir] = oldOtherDirSubTree;
	root -> mySubTree  -> myBal = -MAX(root -> myBal, 0);
	root -> mySubTree  -> myBal = -MIN(root -> myBal, 0);
	root -> myBal = 0;
	return HEIGHT_CHANGE;
};

template<class KeyType>
int
AVLNode <KeyType>::ReBalance(AVLNode <KeyType>  * & root)
{
	int heightChange = HEIGHT_NOCHANGE;
	if(LEFT_INBALANCE (root -> myBal))
	{
		if( root -> mySubTree -> myBal == RIGHT_HEAVY )
		{
		//RL
		heightChange = RotateTwice (root, RIGHT);
		}
		else
		{
			heightChange =  RotateOnce(root, RIGHT);
		}
    }
	else if (RIGHT_INBALANCE(root -> myBal))
	{
		if(root -> mySubTree-> myBal == LEFT_HEAVY)
		{
			//left right rotation
			heightCHange = RotateTwince(root, LEFT);
		}
		else
		{
			heightChange = RotateOnce(root, LEFT);
		}
	}
	return heightChange;
};

template <class KeyType>
cmp_t AVLNode <KeyType>::Compare(KeyType Key, cmp_t cmp) const
{
	switch(cmp)
	{
	case EQ_CMP:
		return myData -> compare(Key);
	case MIN_CMP:
		return (mySubTree)==NULL ? EQ_CMP:MIN_CMP;
	case MAX_CMP:
		return(mySubTree==NULL) ? EQ_CMP:MAX_CMP;
	}
};

template <class KeyType>
Comparable <KeyType> * AVLNode <KeyType>::Search(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp)
{
 cmp_t result;
 while(root && (results = root -> comare(Key, cmp))
 {
  root = root -> mySubTree[(result < 0) ? LEFT : RIGHT];           
 }
};

template <class KeyType>
Comparable <KeyType> * AVLNode <KeyType>::Delete(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp)
{
 cmp_t result;
 while(root && (results = root -> comare(Key, cmp))
 {
  root = root -> mySubTree[(result < 0) ? LEFT : RIGHT];           
 }
};

template <class KeyType>
Comparable <KeyType> * AVLNode <KeyType>::Insert(Comparable<KeyType> *item, AVLNode <KeyType> * & root)
{
	int change;
	return Insert(item, root, change);
};

template <class KeyType>
Comparable <KeyType> AVLNode<KeyType>::Insert(Comparable<KeyType> *item, AVLNode<KeyType> *&root, int & change)
{
	if(root == NULL)
	{
		root = new AVLNode<KeyType>(item);
		Change = HEIGHT_CHANGE;
		return NULL;
	}
	Comparable<KeyType> * found = NULL;
	int increase = 0;
	cmt_t result = root -> compare (item -> Key());
	dir_t dir = (result == MIN_CMP) ? LEFT:RIGHT;
	if(result != EQ_CMP)
	{
		found = Insert(item, root -> mySubTree[dir], change);
		if(found) return found;
		increase = result *change;
	}
	else
	{
		increase = HEIHT_NOCHANGE
		return root -> myData;
		root -> myBal += increase;
		change = (increase && root -> myBal)?(1-Rebaance(root)): HEIGHT_NOCHANGE;
		return NULL;
	}
}


///////////////////////megore
template <class KeyType>
Comparable<KeyType> *
AVLNode<KeyType>::Search(KeyType Key, AVLNode<KeyType> * root, cmp_t cmp)
{
   cmp_t result;
   while (root  &&  (result = root->Compare(Key, cmp))) {
      root = root->mySubTree[(result < 0) ? LEFT : RIGHT];
   }
   return  (root) ? root->myData : NULL;
};


template <class KeyType>
Comparable<KeyType> * AVLNode<KeyType>::Delete(KeyType Key, AVLNode<KeyType> * & root, cmp_t cmp)
{
   int  change;
   return  Delete(Key, root, change, cmp);
};


template <class KeyType>
Comparable<KeyType> *
AVLNode<KeyType>::Delete(KeyType Key, AVLNode<KeyType> * & root, int & change, cmp_t cmp)
{
      // See if the tree is empty
   if (root == NULL) {
         // Key not found
      change = HEIGHT_NOCHANGE;
      return  NULL;
   }

      // Initialize
   Comparable<KeyType> * found = NULL;
   int  decrease = 0;
      // Compare items and determine which direction to search
   cmp_t  result = root->Compare(Key, cmp);
   dir_t  dir = (result == MIN_CMP) ? LEFT : RIGHT;
   if (result != EQ_CMP) {
         // Delete from "dir" subtree 
      found = Delete(Key, root->mySubTree[dir], change, cmp);
      if (! found)  return  found;   // not found - can't delete
      decrease = result * change;    // set balance factor decrement
   } else  {   // Found Key at this node
      found = root->myData;  // set return value

      // ---------------------------------------------------------------------
      // At this point we know "result" is zero and "root" points to
      // the node that we need to delete.  There are three cases:
      //
      //    1) The node is a leaf.  Remove it and return.
      //
      //    2) The node is a branch (has only 1 child). Make "root"
      //       (the pointer to this node) point to the child.
      //
      //    3) The node has two children. We swap items with the successor
      //       of "root" (the smallest item in its right subtree) and delete
      //       the successor from the right subtree of "root".  The
      //       identifier "decrease" should be reset if the subtree height
      //       decreased due to the deletion of the successor of "root".
      // ---------------------------------------------------------------------
      if ((root->mySubTree == NULL) &&
          (root->mySubTree == NULL)) {
             // We have a leaf -- remove it
         delete  root;
         root = NULL;
         change = HEIGHT_CHANGE;    // height changed from 1 to 0
         return  found;
      } else if ((root->mySubTree == NULL) ||
                 (root->mySubTree == NULL)) {
            // We have one child -- only child becomes new root 
         AVLNode<KeyType> * toDelete = root;
         root = root->mySubTree[(root->mySubTree) ? RIGHT : LEFT];
         change = HEIGHT_CHANGE;    // We just shortened the subtree
            // Null-out the subtree pointers so we dont recursively delete
         toDelete->mySubTree = toDelete->mySubTree = NULL;
         delete  toDelete;
         return  found;
      } else {
            // We have two children -- find successor and replace our current
            // data item with that of the successor
         root->myData = Delete(Key, root->mySubTree,
                               decrease, MIN_CMP);
      }
   }
   root->myBal -= decrease;       // update balance factor 
   // ------------------------------------------------------------------------
   // Rebalance if necessary -- the height of current tree changes if one
   // of two things happens: (1) a rotation was performed which changed
   // the height of the subtree (2) the subtree height decreased and now
   // matches the height of its other subtree (so the current tree now
   // has a zero balance when it previously did not).
   // ------------------------------------------------------------------------
   //change = (decrease) ? ((root->myBal) ? balance(root) : HEIGHT_CHANGE)
   //                    : HEIGHT_NOCHANGE ;
   if (decrease) {
      if (root -> myBal) {
         change = ReBalance(root);  // rebalance and see if height changed
      } else {
         change = HEIGHT_CHANGE;   // balanced because subtree decreased
      }
   } else {
      change = HEIGHT_NOCHANGE;
   }
   return  found;
}

static inline void
Indent( int len) {
   for (int i = 0; i < len; i++) {
      cout << ' ';
   }
}

enum TraversalOrder { LTREE, Key, RTREE };

template <class KeyType>
static void
Dump(
     TraversalOrder order,
     const AVLNode<KeyType> * node,
     int level=0)
{
    unsigned  len = (level * 5) + 1;
    if ((order == LTREE) && (node->Subtree(LEFT) == NULL)) {
       Indent( len); 
       cout << "     **NULL**" << endl;
    }
    if (order == Key) {
       Indent( len); 
       cout << node->Key() << ":" << node->Bal() << endl;
    }
    if ((order == RTREE) && (node->Subtree(RIGHT) == NULL)) {
       Indent( len); 
       cout << "     **NULL**" << endl;
    }
}

template <class KeyType>
static void
Dump(const AVLNode<KeyType> * node, int level=0)
{
   if (node == NULL) {
      cout << "***EMPTY TREE***" << endl;
   } else {
      Dump( RTREE, node, level);
      if (node->Subtree(RIGHT)  !=  NULL) {
         Dump( node->Subtree(RIGHT), level+1);
      }
      Dump( Key, node, level);
      if (node->Subtree(LEFT)  !=  NULL) {
         Dump( node->Subtree(LEFT), level+1);
      }
      Dump(LTREE, node, level);
   }// if non-empty tree
}

template <class KeyType>
void
AvlTree<KeyType>::DumpTree() const {
   Dump(myRoot);
}

// Sample main code

main()
{
    char stop;
    AvlTree<long> tree;
    Comparable<long> * found = NULL;
    long inputValue;
	Comparable<long> *myarray[25];

	
	int numVoters;
	ifstream inputFile;

	inputFile.open("testvals.txt");
	if (!inputFile)
		cout<<"Error on opening file"<<endl;
	numVoters = 0;
	while (!inputFile.eof()&& numVoters < 25)
	{
        inputFile>>inputValue;
		myarray[numVoters] = new Comparable<long>(inputValue);
		numVoters++;
	}
	cout<<" Initial Input"<<endl;
    for (int i = 0; i<numVoters; i++)
      {
             cout<<myarray[i]->Key()<<endl;
      }
     int  i;
    for (i = 0 ; i < numVoters ; i++)  {
       cout << "+++ inserting Key #" << i+1 << ": " << myarray[i]->Key() << endl;
       found = tree.Insert(myarray[i]);
       if (found) {
          cout << "\t(already in tree)\n";
       }
      }
    tree.DumpTree();
    cin >> stop;
        system("PAUSE");
    return EXIT_SUCCESS; 
};

Valkyriecoder 0 Newbie Poster · Answer 3 · 2009-03-02T09:25:35+00:00

what are you acomplishing by that code? its huge man

deerowbear 0 Newbie Poster · Answer 4 · 2009-03-02T09:30:04+00:00

I am trying to create an balanced AVLTree. Most of the code was given by instructor, but I must have copied the code wrong. I am getting about 100 errors. : (

daviddoria 334 Posting Virtuoso Featured Poster · Answer 5 · 2009-03-02T18:22:16+00:00

We can't help you with 100 errors, especially if we don't know what they are. You need to narrow down the problem to < 20 lines of code and ask a specific question.

Ancient Dragon 5,243 Achieved Level 70 Team Colleague Featured Poster · Answer 6 · 2009-03-02T20:25:57+00:00

Post just the first 2 error messages and the line on which the error appears. Then maybe someone can help you with that.

compile errors

Recommended Answers Collapse Answers

All 8 Replies

Recommended Answers