pa2.cpp

using C++ to build AVL tree and functions

/*
 * Name: Fok On Man
 * Student ID: 06035253
 * Lecture Section: L1
 * Tutorial Section: T1C
 * I did not cheat in this assignment.
 */

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

// Structure of the node of the AVL tree
struct avlnode {
	int sal;
	avlnode *left;
	avlnode *right;
	int height;
};

int count(avlnode *&ptr);									// Count the total number of node under the root
int height (avlnode *ptr);									// Return the height of the node
void single_left(avlnode *&k2);							// Single rotation with left node
void single_right(avlnode *&k2)	;					// Single rotation with right node
void double_left(avlnode *&k3);						// Double rotation with left node
void double_right(avlnode *&k3)	;					// Double rotation with right node

void insert(avlnode *&ptr, int salary);				// Insert a new node
void add(avlnode *&ptr, int amount);					// Increase the salary of all the nodes
void sub(avlnode *&ptr, int amount, int lower);	// Decrease the salary of all the nodes
int find(avlnode *&ptr, int i);								// Return the value of the position


int count(avlnode *&ptr)
{
	if (ptr == NULL)
		return 0;
	else return (1 + count(ptr->left) + count(ptr->right));			// Recursion to count the nodes in left subtree and right subtree
}

int count(avlnode *&ptr, int lower)
{
	if (ptr == NULL)
		return 0;
	if (ptr->sal >= lower)
		return (1 + count(ptr->right, lower) + count(ptr->left, lower));
	else return count(ptr->right, lower) + count(ptr->left, lower);
}

int height( avlnode *ptr )
{
	if (ptr == NULL)
		return -1;
	else return ptr->height;													// Return the height of the node
}

void single_left(avlnode *&k2)
{
	avlnode *k1 = k2->left;
	k2->left = k1->right;
	k1->right = k2;
	k2->height = max(height(k2->left), height(k2->right)) + 1;
	k1->height = max(height(k1->left), k2->height) + 1;
	k2 = k1;
}

void single_right(avlnode *&k2)
{
	avlnode *k1 = k2->right;
	k2->right = k1->left;
	k1->left = k2;
	k2->height = max(height(k2->right), height(k2->left)) + 1;
	k1->height = max(height(k1->right), k2->height) + 1;
	k2 = k1;
}

void double_left(avlnode *&k3)
{
	single_right(k3->left);
	single_left(k3);
}

void double_right(avlnode *&k3)
{
	single_left(k3->right);
    single_right(k3);
}

void insert(avlnode *&ptr, int salary)
{
	if (ptr == NULL)																// Base case, to create a new node
	{
		ptr = new avlnode;
		ptr->sal = salary;
		ptr->left = NULL;
		ptr->right = NULL;
		ptr->height = 0;
	}
	else if (salary < ptr->sal)
	{
		insert(ptr->left, salary);												// Recursion to find the position to insert node
		 if (height(ptr->left) - height(ptr->right) == 2)
			if (salary < ptr->left->sal)
				single_left(ptr);
			else
				double_left(ptr);
	}
	else if (salary >= ptr->sal)
	{
		insert(ptr->right, salary);												// Recursion to find the position to insert node
		if (height(ptr->right) - height(ptr->left) == 2)
			if (salary >= ptr->right->sal)
				single_right(ptr);
			else
				double_right(ptr);
	}
	ptr->height = max(height(ptr->left), height(ptr->right)) + 1;
}

void add(avlnode *&ptr, int amount)
{
	if (ptr == NULL)
		return;
	ptr->sal += amount;															// Add all the salary by recursion
	add(ptr->right, amount);
	add(ptr->left, amount);
};

void sub(avlnode *&ptr, int amount, int lower)
{
	if (ptr == NULL)
		return;
	ptr->sal -= amount;															// Substract all the salary by recursion
	sub(ptr->left, amount, lower);
	sub(ptr->right, amount, lower);
};

int find(avlnode *&ptr, int i)
{
	if (ptr == NULL)
		return 0;

	int num = count(ptr);

	if (num == 1)																	// Base case for only one node
		return ptr->sal;
	if (num == 2)																	// Base case for only two nodes
	{
		if (ptr->right == NULL)
		{
			if (i == 1)
				return ptr->sal;
			else return ptr->left->sal;
		}
		else
		{
			if (i == 2)
				return ptr->sal;
			else return ptr->right->sal;
		}
	}
	if (num <= 3)																	// Base case for only three nodes
	{
		if (i == 1)
			return ptr->right->sal;
		if (i == 2)
			return ptr->sal;
		if (i == 3)
			return ptr->left->sal;
	}

	if (i == count(ptr->right)+1)												// For the root of the tree
		return ptr->sal;
	else if (i > count(ptr->right))											// Node is in left subtree
		return find(ptr->left, i-count(ptr->right)-1);
	else
		return find(ptr->right, i);												// Node is in right subtree
}

int main()
{
    string command;
    int lower, amount, i;
    avlnode *cur = NULL;

    cout<< "Welcome to the simple accountant program. :)"<< endl;
    cout<< "Please input the lower bound of salary."<< endl;
    cin>> lower;

    do
	{
		cout<< "Command>";
		cin>> command;

		if (command == "Insert")												// For the command "Insert"
		{
			cin>> amount;
			if (amount >= lower)
				insert(cur, amount);
			cout<< "Current total number of employees is "<< count(cur)<< endl;
		}
		else if (command == "Add")											// For the command "Add"
		{
			cin>> amount;
			add(cur, amount);
		}
		else if (command == "Sub")											// For the command "Sub"
		{
			cin>> amount;
			sub(cur, amount, lower);
			cout<< "Current total number of employees is "<< count(cur, lower)<< endl;
		}
		else if (command == "Find")											// For the command "Find"
		{
			cin>> amount;
			if (amount > count(cur))
				cout<< "-1"<< endl;
			else
			{
				i = find(cur, amount);
				if (amount == 1)
					cout<< "The 1st ";
				else if (amount == 2)
					cout<< "The 2nd ";
				else if (amount ==3)
					cout<< "The 3rd ";
				else cout<< "The "<< amount<<"th ";
				cout<< "salary in the salary sequence is "<< i<< endl;
			}
		}
		else if (command == "Quit")											// For the command "Quit"
			exit(1);
		else
		{
			cerr<< "Command Error!"<< endl;
		}
	 }while (command != "Quit");
     return 0;
 }