A hash table and AVL tree to store and retrieve student student data

AVLTree.h

// CSCI 3333 Data Structures & Algorithms
// Alex Marroquin
// 9-21-12
// Hwk #4: Speed Table - AVLTree.h


//AVL tree used to store student data

#include<iostream>
#include<string>
using namespace std;

template<class THING>
class AVLTree
{
private:
	class node
	{
	public:
		THING data;
		node * right;
		node * left;

		int height;

		node(THING x)
		{
			data=x;
			right=NULL;
			left=NULL;

			height = 0;
		}
	};


	node * root;
	
	//rotation methods
	void leftRotation(node * &r)
	{
		bool t = false;  //This is in case the root needs to be moved, it changed it incorrectly if without this variable
		if(r == root)
			t = true;
		node * a;
		node * b;
		node * bleft;

		a= r;
		b= r->right;
		bleft = b->left;

		r = b;
		b->left = a;
		a->right = bleft;

		//heights might have changed
		a->height = 1 + max( height(a->left), height(a->right) );
		b->height = 1 + max( height(b->left), height(b->right) );
		if(t)
			root = b;
	}

	void rightRotation(node * &r)
	{
		bool t = false; // Same as before
		if(r == root)
			t = true;
		node * a;
		node * b;
		node * bright;

		a= r;
		b= r->left;
		bright = b->right;

		r = b;
		b->right = a;
		a->left = bright;

		//heights might have changed
		a->height = 1 + max( height(a->left), height(a->right) );
		b->height = 1 + max( height(b->left), height(b->right) );
		if(t)
			root = b;
	}

	void rightLeftRotation(node * &r)
	{
		rightRotation(r->right);
		leftRotation(r);
	}

	void leftRightRotation(node * &r)
	{
		leftRotation(r->left);
		rightRotation(r);
	}

	//get height of node
	int height(node * r)
	{
		if( r == NULL )
			return -1;
		else
			return r->height;
	}

	//insert x into tree rooted at pointer r
	void recInsert(THING x, node * &r)
	{
		if( r == NULL ) //empty tree
		{
			r = new node(x);
		}
		else  //nodes are in the tree
		{
			if( x > r->data )  //go right
			{
				recInsert(x, r->right);
				
				//check for imbalance
				if( height(r->right) > height(r->left) +1 )
				{
					if( height(r->right->right) > height(r->right->left) )
					{
						leftRotation(r);
					}
					else
					{
						rightLeftRotation(r);
					}
				}
			}
			else  //go left
			{
				recInsert(x, r->left);

				//check for imbalance
				if( height(r->left) > height(r->right) + 1 )
				{
					if( height(r->left->left) > height(r->left->right) )
					{
						rightRotation(r);
					}
					else
					{
						leftRightRotation(r);
					}
				}
			}
		}

		//update height becuz it might have changed
		r->height = 1+ max(height(r->right), height(r->left));
	}
	//For balancing after deleting a node
	void balance(node *&search)
	{
		if( height(search->right) > height(search->left) +1 )
		{
			if(height(search->right) - height(search->left) == 2)
			{
				leftRotation(search);
			}
			else
			{
				if( height(search->right->right) > height(search->right->left) )
				{
					leftRotation(search);
				}
				else
				{
					rightLeftRotation(search);
				}
			}
		}
		//
		if( height(search->left) > height(search->right) + 1 )
		{
			if(height(search->left) - height(search->right) == 2)
			{
				rightRotation(search);
			}
			else
			{
				if( height(search->left->left) > height(search->left->right) )
				{
					rightRotation(search);
				}
				else
				{
					leftRightRotation(search);
				}
			}
		}
	}

	void removenode(THING x, node *&search)
	{
		if(search == NULL)
		{
			cout<<"No such value found . . ."<<endl;
			return;
		}
		else if(search->data == x)
		{
			//Leaf Case
			if(search->left == NULL && search->right == NULL)
			{
				search = NULL;
				return;
			}
			//1 Child Case
			else if(search->left == NULL && search->right != NULL)
			{
				node *r = search->right;
				search->data = search->right->data;
				search->left = search->right->left;
				search->right = search->right->right;
				delete r;
			}
			//1 Child Case
			else if(search->left != NULL && search->right == NULL)
			{
				node *l = search->left;
				search->data = search->left->data;
				search->right = search->left->right;
				search->left = search->left->left;			
				delete l;
			}
			//2 Children Case
			else if(search->left != NULL && search->right != NULL)
			{
				node *max = findMax(search->left);
				node *smax = findSecondMax(search->left);
				search->data = max->data;
				if(smax != NULL)
				{
					bool t = false;
					if(search->left == smax)
						t = true;
					smax->right = max->left;
					balance(smax);
					if(t)
						search->left = smax;
				}
				if(max == search->left)
					search->left = search->left->left;
				
				delete max, smax;
			}
		}
		else if(x < search->data)
		{
			removenode(x,search->left);
		}
		else if(x > search->data)
		{
			removenode(x,search->right);
		}
		//This should balance the tree
		balance(search);
		//
	}
	//display items in tree rooted at r
	void recDisplay(node * r)
	{
		if( r == NULL )
		{
			//do nothing!!!!!
		}
		else
		{
			recDisplay(r->left);
			cout << r->data << endl;
			recDisplay(r->right);
		}
	}

	int recHeight(node * r)
	{
		if( r == NULL )
		{
			return -1;
		}
		else
		{
			return 1 + max( recHeight(r->right), recHeight(r->left) );
		}
	}

	
public:

	AVLTree()
	{
		root = NULL;
	}

	void insert(THING x)
	{
		recInsert(x, root);
	}

	void remove(THING x)
	{
		node *search = root;
		removenode(x,search);
	}

	void display()
	{
		recDisplay(root);
	}

	int computeHeight()
	{
		return height(root);
		//return recHeight(root);
	}

	node *findMax(node *h)
	{
		node *max;
		if(h->right == NULL)
			return h;
		else
			max = findMax(h->right);
		return max;
	}
	node *findSecondMax(node *h)
	{
		node *smax;
		if(h->right == NULL)
			return NULL;
		if(h->right->right == NULL)
			return h;
		else
			smax = findSecondMax(h);
		return smax;
	}
};

speedTable.h

// CSCI 3333 Data Structures & Algorithms
// Alex Marroquin
// 9-21-12
// Hwk #4: Speed Table - speedTable.h

//Hash Table
//Calls on studentList to generate an array of students, basically an array of array
//that can resize itself

#include "studentList.h"


class speedTable
{
private:
      studentList * table; //an array of studentLists
      int tableSize;       //size of the array
	  double numItems;
 
public:
      //constructor which will allocate a new array of studentLists of size ‘size’
      speedTable(int size){table = new studentList[size];tableSize = size;numItems = 0;};
     
      //be sure to free all dynamically allocated memory!
      ~speedTable();
 
      //add student s to data structure
      void add(student s);
     
      //remove student with given id from data structure
      void remove(int id);
 
      //locate and return the student with given id from the data structure
      student getStudent(int id);
 
      //Do this method last.  Create a new array of size newsize and rehash
      //all items in the old table into the new table.
      //Free (delete) the old array and point the table
      //variable at the new array.
      void resize(int newsize);
      
      void dispTable();
      
};
void speedTable::add(student s)
{
   if(numItems/tableSize >= 1)
   {   
	   cout<<"There are "<<numItems<<" items in a size "<<tableSize<<" list"<<endl;
	   resize(3*tableSize);
	   cout<<"Enlarge from "<<tableSize/3<<" to "<<tableSize<<endl;
   }
   int place = s.id%tableSize;   
   //Linear Probing
   while(!table[place].empty())
   {
	   place += 1;
	   if(place == tableSize)
		   place = 0;
   }
   table[place].push(s);  
   numItems++;
}
void speedTable::remove(int id)
{
   int place = id%tableSize;
   table[place].removeStudent(id);
   while(table->getStudent(id).id == id)
   {
	   table[place+1].removeStudent(id);
   }
   numItems--;
   if((numItems)/tableSize <= 0.25)
   {
	   cout<<"There are "<<numItems<<" items in a size "<<tableSize<<" list"<<endl;
	   resize(tableSize/3);
	   cout<<"Cut from "<<tableSize*3<<" to "<<tableSize<<endl;
   }
}
student speedTable::getStudent(int id)
{
   int place = id%tableSize;
   student s = table[place].getStudent(id);
   return s;
}
void speedTable::dispTable()
{
   for(int i = 0; i < tableSize; i++)
   {
      cout<<"Table row "<<i<<endl;
      table[i].display();
   }
   cout<<"Table Size: "<<tableSize<<endl;
   cout<<"# of students: "<<numItems<<endl;
   cout<<"Load Factor (LF): "<<numItems/tableSize<<endl<<endl;
}
void speedTable::resize(int newsize)
{
   studentList * dummy = new studentList[newsize];
   student s;
   int place;
   for(int i = 0; i < tableSize; i++)
   {
      while(!table[i].empty())
      {
         s = table[i].pop();
         place = s.id%newsize;
		 while(!dummy[place].empty())
		 {
			 place += 1;
			 if(place == tableSize)
			 {	 
				 place = 0;
			 }
		 }
         dummy[place].push(s);
      }
   }
   table = dummy;
   tableSize = newsize;
}
speedTable::~speedTable()
{
   for(int i = 0; i < tableSize; i++)
   {
      table[i].~studentList();
   }
}

StudentList.cpp

// CSCI 3333 Data Structures & Algorithms
// Alex Marroquin
// 9-28-12

//Hash Table Implementation
//The hash table stores student data in speedTable, a hash table
//A second implementation afterwards stores the data in an AVL Tree

#include <cstdlib>
#include <iostream>
#include <string>
#include "speedTable.h"
#include "AVLTree.h"

using namespace std;

int main()
{
	//speedTable students(10);
	cout<<"Hash Table"<<endl;
	speedTable students(10); 
    student Jay("Jay",155,"UTPA");
    student Bay("Bay",245,"UT Austin");
    student Quake("Quake",446,"UTB");
	student Bad("Bad",123,"UTB");
	student Jake("Jake",100,"UT Dallas");
	student Blake("Blake",451,"Rice");
	student Sar("Sar",777,"MIT");
	student Borr("Borr",142,"Rice");
	student Nope("Nope",564,"Nowhere");
	student Bleh("Bleh",148,"Drexel");
	student Blah("Blah",899,"York");
	student York("York",555,"York");
    students.add(Jay);		//155   #1
    students.add(Quake);	//446	#2
    students.add(Bay);		//245	#3
	students.add(Bad);		//123	#4
	students.add(Jake);		//100	#5
	students.add(Blake);	//451	#6
	students.add(Sar);		//777	#7
	students.add(Borr);		//142	#8
	students.add(Nope);		//564	#9
	students.add(Bleh);		//148	#10
	students.add(Blah);		//899	#11
	students.add(York);		//555	#12
    students.dispTable();

	students.remove(899);
	students.remove(555);
	students.remove(123);
	students.remove(777);
	students.remove(142);
	students.remove(564);
	students.remove(451);
	students.dispTable();
	
	string a;
	cout<<"Type something to clear the screen & move on to next part. ";
	cin>>a;
	system("cls");
	//AVL Tree
	cout<<"AVL Tree"<<endl;
	AVLTree<int> tree;
	tree.insert(8);
	tree.insert(4);
	tree.insert(6);
	tree.insert(5);
	tree.insert(9);
	tree.insert(15);
	tree.insert(12);
	tree.insert(27);
	tree.insert(7);
	tree.insert(55);
	tree.insert(67);
	tree.insert(101);
	tree.insert(45);
	tree.insert(56);
	tree.insert(70);
	tree.display();
	cout<<"Tree height1: "<<tree.computeHeight()<<endl;
	tree.remove(9);
	tree.display();
	cout<<"Tree height2: "<<tree.computeHeight()<<endl;
	tree.remove(8);
	tree.display();
	cout<<"Tree height3: "<<tree.computeHeight()<<endl;
	tree.remove(7);
	tree.display();
	cout<<"Tree height4: "<<tree.computeHeight()<<endl;
	system("pause");
	return 0;
}

studentList.h

// CSCI 3333 Data Structures & Algorithms
// Alex Marroquin
// 9-21-12
// Hwk #4: Speed Table - studentList.h
#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;
class student
{
public:
      int id;            //student ID number
      string name;       //student’s name
      string university; //student’ university
	  student(){};
	  student(string nm, int ID, string univ){name = nm; id = ID; university = univ;};
};
 
//student list is a doubly linked list of students. 
class studentList
{
private:
      class node
      {
      public:
            student data;
            node * next;
            node * prev;
			node(){prev = NULL; next = NULL;};
			node(student s){data = s; prev = NULL; next = NULL;};
      };
     
      node * head;
      
 
public:
      studentList();
 
      //be sure to free all dynamically allocated memory!
      ~studentList(); 
 
      //return true if the list is empty, false if not
      bool empty();
 
      //insert student s into the front of the linked list
      void push(student s);
 
      //remove and return the student at the front of the list
      student pop();
 
      //locate and remove the student with given ID number
      void removeStudent(int id);
 
      //locate and return a copy of the student with given ID number
      student getStudent(int id);
 
      //arrange students into increasing based on either ID or name.  If
      //variable 'field' has value "id", sort into increasing order by id.
      //If 'field' has value "name", sort into alphabetical order by name.
      void sort(string field);
 
      //a test function to simply display the list of students to the screen
      //in the order they appear in the list.
      void display();

	  void idsort();
	  void namesort();
	  void remove(node *s);
	  student findSmallestID();
	  student findAlpha();
};
studentList::studentList()
{
  head = NULL;
}
studentList::~studentList()
{
    while(!empty())
    {
      node* temp = head;
      head=head->next;
      delete temp;
    }
}
bool studentList::empty()
{
     if(head == NULL)
     {
       return true;
     }
     return false;      
}
student studentList::findSmallestID()
{
	node *search = head;
	node *temp = head;
	while(search != NULL)
	{
		if(search->data.id < temp->data.id)
		{
			temp = search;
		}
		search = search->next;
	}

	return temp->data;
}
student studentList::findAlpha()
{
	node *search = head;
	node *temp = head;
	while(search != NULL)
	{
		if(search->data.name < temp->data.name)
		{
			temp = search;
		}
		search = search->next;
	}

	return temp->data;
}
void studentList::idsort()
{
	node *temp = NULL; // temporary storage for nodes
	node *search = head; // for searching through list
	node *temphead = NULL;
	student small;
	
	while(!empty())
	{
		small = findSmallestID();
		
		if(temphead == NULL)
		{
			temp = new node(small);
			temphead = temp;
		}
		else
		{
			temp->next = new node(small);
			temp->next->prev = temp;
			temp = temp->next;
		}
		removeStudent(small.id);
	}
	head = temphead;
	cout<<"A sorted list by ID!!!"<<endl<<endl;
}
void studentList::namesort()
{
	node *temp = NULL; // temporary storage for nodes
	node *search = head; // for searching through list
	node *temphead = NULL;
	student small;
	
	while(!empty())
	{
		small = findAlpha();
		
		if(temphead == NULL)
		{
			temp = new node(small);
			temphead = temp;
		}
		else
		{
			temp->next = new node(small);
			temp->next->prev = temp;
			temp = temp->next;
		}
		removeStudent(small.id);
	}
	head = temphead;
	cout<<"A sorted list by names!!!"<<endl<<endl;
}
void studentList::sort(string field)
{
	if(field == "id" || field == "ID")
	{
		idsort();
	}
	else if(field == "name" || field == "NAME")
	{
		namesort();
	}

}
student studentList::getStudent(int id)
{
	//cout<<"Searching for student . . ."<<endl;
	node *search = head;
	student wanted("No Student",00,"No School");
	while(search != NULL)
	{
		if(search->data.id == id)
		{
			wanted = search->data;
		}
		search = search->next;
	}
	return wanted;
}
void studentList::push(student s)
{
     if(head == NULL)
     {
       node *temp = new node(s);
       head = temp;
     }
     else
     {
        node *dummy = new node(s);
        dummy->next = head;
        head->prev = dummy;
        head = dummy;
     }
}
student studentList::pop()
{
	node *temp = head;
	if(head == NULL)
	{
		cout<<"No students anymore."<<endl;
		student s("None",0,"None");
		return s;
	}
	if(head->next != NULL)
	{
		head->next->prev = NULL;
	}
	head = temp->next;
	//cout<<"POP!!!"<<endl<<endl;
	return temp->data;
}
void studentList::remove(node *s)
{
	if(s->prev == NULL && s->next == NULL)
	{
		head = NULL;
		return;
	}
	if(s == head)
	{
		head = head->next;
		head->prev = NULL;
	}
	node *temp1 = s->prev;
	node *temp2 = s->next;
	if(s->prev != NULL)
	{
		temp1->next = temp2;
	}
	if(s->next != NULL)
	{
		temp2->prev = temp1;
	}
}
void studentList::removeStudent(int id)
{
	node *search = head;
	if(head == NULL || empty())
	{
			cout<<"No students anymore."<<endl;
			return;
	}
	while(search != NULL)
	{
		if(search->data.id == id)
		{
			remove(search);
		}
		search = search->next;
	}
}
void studentList::display()
{
     if(head != NULL)
     {
       node *current = head;
       while(current != NULL)
       {
         cout<<current->data.name<<" "<<current->data.id<<" "<<current->data.university<<endl;
		 current = current->next;
       }
	   cout<<endl<<endl;
     }
}