//CS222 Program 5, AVL tree with delete
//Shawn O'Neil
#include <iostream>
#include <string>
#include "tree1.h"
using namespace std;
#define EMPTYTREE 1
#define DUPLICATE 2
#define NOMATCH 3
#define OUTRANGE 4
#define NONONZERO 5
//tree constructor
Tree::Tree()
{
root = NULL;
}
//tree destructor
Tree::~Tree()
{
delete root;
}
//adds a node to the tree
void Tree::add(string name)
{
if(root == NULL)
{
root = new Node();
root->setname(name);
root->setparent(NULL);
}
else
root->add(name, root);
}
//sets a grade for the node of thename
void Tree::grade(int number, double score, string thename)
{
if(number != 1 && number != 2 && number != 3 && number != 4 && number != 5)
throw OUTRANGE;
if(score < 0)
throw OUTRANGE;
else if(root != NULL)
root->grade(number, score, thename);
else
throw EMPTYTREE;
}
//prints the tree
void Tree::print()
{
if(root != NULL)
root->print();
else
throw EMPTYTREE;
}
//deletes a node from the tree, with the name of name
void Tree::del(string name)
{
if(root != NULL)
root->del(name, root);
else
throw EMPTYTREE;
}
//gets the mean of all the nonzero particular exams in the tree
double Tree::mean(int exam)
{
if(exam != 1 && exam != 2 && exam != 3 && exam != 4 && exam != 5)
throw OUTRANGE;
else if(root != NULL)
{
double total = root->gettotal(exam);
double number = root->getnumber(exam);
if(number != 0)
return total/number;
else
throw NONONZERO;
}
else
throw EMPTYTREE;
}
//checks to see if the tree is empty. dont think its actually used...
bool Tree::empty()
{
return root == NULL;
}
//node constructor
Node::Node()
{
parent = left = right = NULL;
grade1 = grade2 = grade3 = grade4 = grade5 = 0;
height = 0;
}
//node destructor
Node::~Node()
{
if(left != NULL)
delete left;
if(right != NULL)
delete right;
//cout << "destructing: " << name << endl;
}
//adds a name to the tree, *&root is used by by the computeheights method, for the AVL in case it needs to rotate and set a new root
void Node::add(string thename, Node *&root)
{
if(name != thename)
{
if(thename < name)
{
if(left != NULL)
left->add(thename, root);
else
{
left = new Node();
left->setparent(this);
left->setname(thename);
left->computeheights(root);
}
}
else
{
if(right != NULL)
right->add(thename, root);
else
{
right = new Node();
right->setparent(this);
right->setname(thename);
right->computeheights(root);
}
}
}
else
throw DUPLICATE;
}
//sets the node n as a child of the current node
void Node::resetchild(Node *n)
{
string thename = n->getname();
if(thename < name)
left = n;
else
right = n;
n->setparent(this);
}
//sets the child with the name thename to null. used when deleting a node
void Node::setchildtonull(string thename)
{
//cout << "setting " << thename << " to null. left is " << endl;// left->getname() << " right is " << right->getname() << endl;
if(left != NULL)
if(left->getname() == thename)
left = NULL;
if(right != NULL)
if(right->getname() == thename)
right = NULL;
}
//returns the name
string Node::getname()
{
return name;
}
//returns a particular grade
double Node::getgrade(int number)
{
if(number == 1)
return grade1;
else if(number == 2)
return grade2;
else if(number == 3)
return grade3;
else if(number == 4)
return grade4;
else
return grade5;
}
//gets total number of nodes with nonzero grades from this point down
double Node::getnumber(int exam)
{
double total = 0;
if(exam == 1 && grade1 != 0)
total += 1;
else if(exam == 2 && grade2 != 0)
total += 1;
else if(exam == 3 && grade3 != 0)
total += 1;
else if(exam == 4 && grade4 != 0)
total += 1;
else if(exam == 5 && grade5 != 0)
total += 1;
if(left != NULL)
total = total + left->getnumber(exam);
if(right != NULL)
total = total + right->getnumber(exam);
return total;
}
//gets total of the grades for exam number exam from this point down
double Node::gettotal(int exam)
{
double mytotal = 0;
if(exam == 1)
mytotal = mytotal + grade1;
else if(exam == 2)
mytotal = mytotal + grade2;
else if(exam == 3)
mytotal = mytotal + grade3;
else if(exam == 4)
mytotal = mytotal + grade4;
else if(exam == 5)
mytotal = mytotal + grade5;
if(left != NULL)
mytotal = mytotal + left->gettotal(exam);
if(right != NULL)
mytotal = mytotal + right->gettotal(exam);
return mytotal;
}
//this is used to get the immediate successor of a node, short version used by delete
Node * Node::slideleft()
{
if(left == NULL)
return this;
else
return left->slideleft();
}
//deletes a node from the tree. if the node we want to delete is the parent,
//then it usees *&root to set the root of the tree
void Node::del(string thename, Node *&root)
{
if(name == thename)
{
if(left == NULL && right == NULL)
{
if(parent != NULL)
{
parent->setchildtonull(name);
parent->computeheights(root);
}
else
root = NULL;
delete this;
}
else if(left == NULL)
{
if(parent != NULL)
{
Node *q = parent;
q->resetchild(right);
q->computeheights(root);
}
else
{
root = right;
right->setparent(NULL);
}
right = NULL;
delete this;
}
else if(right == NULL)
{
if(parent != NULL)
{
Node *q = parent;
q->resetchild(left);
q->computeheights(root);
}
else
{
root = left;
left->setparent(NULL);
}
left = NULL;
delete this;
}
else
{
Node *p = right->slideleft();
name = p->getname();
grade1 = p->getgrade(1);
grade2 = p->getgrade(2);
grade3 = p->getgrade(3);
grade4 = p->getgrade(4);
grade5 = p->getgrade(5);
p->del(p->getname(),root);
}
}
else
{
if(thename < name)
{
if(left == NULL)
throw NOMATCH;
else
left->del(thename, root);
}
else
{
if(right == NULL)
throw NOMATCH;
else
right->del(thename, root);
}
}
}
//sets the parent node
void Node::setparent(Node *n)
{
parent = n;
}
//sets the name, duh
void Node::setname(string thename)
{
name = thename;
}
//Returns the mean of all the nonzero scores on a particular test from this point down
double Node::mean(int exam)
{
double leftmean = 0;
double rightmean = 0;
double memean = 0;
if(exam == 1)
memean = grade1;
else if(exam == 2)
memean = grade2;
else if(exam == 3)
memean = grade3;
else if(exam == 4)
memean = grade4;
else if(exam == 5)
memean = grade5;
if(right != NULL)
rightmean = right->mean(exam);
if(left != NULL)
leftmean = left->mean(exam);
int count = 0;
if(leftmean != 0)
count++;
if(rightmean != 0)
count++;
if(memean != 0)
count++;
if(count == 0)
return 0;
return (leftmean+rightmean+memean)/count;
}
// Sets the grade for a particular test for the node.
void Node::grade(int number, double score, string thename)
{
if(name == thename)
{
if(number == 1)
grade1 = score;
else if(number == 2)
grade2 = score;
else if(number == 3)
grade3 = score;
else if(number == 4)
grade4 = score;
else if(number == 5)
grade5 = score;
}
else if(thename < name)
{
if(left != NULL)
left->grade(number, score, thename);
else
throw NOMATCH;
}
else
{
if(right != NULL)
right->grade(number, score, thename);
else
throw NOMATCH;
}
}
int Node::getheight()
{
return height;
}
void Node::computeheights(Node *&root)
{
int lh = 0;
int rh = 0;
if(left == NULL && right == NULL)
{
height = 1;
if(parent != NULL)
parent->computeheights(root);
}
else
{
if(left != NULL)
lh = left->getheight();
if(right != NULL)
rh = right->getheight();
if(rh - lh > 1) //too heavy on the right
{
//cout << "too heavy on right" << endl;
int zigheight = 0;
int dirheight = 0;
if(right != NULL)
if(right->left != NULL)
zigheight = right->left->getheight();
if(right != NULL)
if(right->right != NULL)
dirheight = right->right->getheight();
if(zigheight > dirheight) //needs a double rotation
{
right->rotateright(root); //tell the those two to recomputer their heights w/out recursion
Node *q = parent;
rotateleft(root);
if(q != NULL)
q->computeheights(root);
}
else //single rotation
{
Node *q = parent;
rotateleft(root); //add a part to recompute the heigts of the two invovled w/out recursion
if(q != NULL)
q->computeheights(root);
}
}
else if(lh - rh > 1) //too heavy on the left
{
//cout << "too heavy on left" << endl;
int zigheight = 0;
int dirheight = 0;
if(left != NULL)
if(left->right != NULL)
zigheight = left->right->getheight();
if(left != NULL)
if(left->left != NULL)
dirheight = left->left->getheight();
if(zigheight > dirheight) //double rotation
{
left->rotateleft(root);
Node *q = parent;
rotateright(root);
if(q != NULL)
q->computeheights(root);
}
else //single rotation
{
Node *q = parent;
rotateright(root);
if(q != NULL)
q->computeheights(root);
}
}
else //not heavier on either side, computer my height and pass it up
{
//cout << "still avl from here down" << endl;
if(lh > rh)
height = lh + 1;
else
height = rh + 1;
if(parent != NULL)
parent->computeheights(root);
}
}
//if rh and lh are more than one off, rotate
//but first check to see if the zigzag child is greater than the height of the direct grandchild
//if so, rotate zigzag child up twice (i.e., rotate zigzag grandchild up(absolute recomputing the two involved), then have it call its new parent
//compute heights (recursive) CASE DOUBLE ROTATION?
//recompute the heigts of yourself and THEN the other one that you rotated (the two involved) based off of what
//know their childrens heights are, but dont recurse this up the tree, so make a definatecomputeheights method.
}
Node * Node::getleft(){
return left;}
void Node::setleft(Node *n){
left = n;}
Node * Node::getright(){
return right;}
void Node::setright(Node *n){
right = n;}
void Node::absheight(){
int lh = 0;
int rh = 0;
if(left != NULL)
lh = left->getheight();
if(right != NULL)
rh = right->getheight();
if(rh > lh)
height = rh + 1;
else
height = lh + 1;}
void Node::rotateleft(Node *&root){
Node *q = parent;
Node *r = right;
Node *z = r->getleft();
parent = r;
r->setleft(this);
right = z;
if(z != NULL) z->setparent(this);
if(q == NULL) root = r;
else q->resetchild(r);
r->setparent(q);
absheight();
r->absheight();
//cout << "Rotated left. " << endl;
}
void Node::rotateright(Node *&root){
Node *q = parent;
Node *l = left;
Node *z = l->getright();
parent = l;
l->setright(this);
left = z;
if(z != NULL) z->setparent(this);
if(q == NULL) root = l;
else q->resetchild(l);
l->setparent(q);
absheight();
l->absheight();
//cout << "Rotated right. " << endl;
}
//Print method for the node, inorder. Prints name, and grades.
void Node::print()
{
if(left != NULL)
left->print();
cout << name << " : " << grade1 << " , " << grade2 << " , " << grade3 << " , " << grade4 << " , " << grade5 << endl;//" height: " << height <<endl;
if(right != NULL)
right->print();
}
int main(int argc, char ** argv)
{
cout << "Happy birthday euclid." << endl;
Tree t;
string action;
int number;
double grade;
string name;
while(cin >> action, cin)
{
cin.ignore();
if(action == "ADD")
{
getline(cin, name);
try
{
t.add(name);
cout << "Successfully added " << name << "." << endl;
cout << endl;
}
catch(int e)
{
if(e == NOMATCH)
cout << "Could not add, ERROR" << endl;
else if(e == EMPTYTREE)
cout << "Could nto add, ERROR" << endl;
else if(e == DUPLICATE)
cout << "Could not add " << name << ". Name already exists." << endl;
else if(e == OUTRANGE)
cout << "Could not add, ERROR" << endl;
cout << endl;
}
}
else if(action == "PRINT")
{
try
{
// cout << endl;
cout << "Statistics: " << endl;
t.print();
cout << endl;
}
catch(int e)
{
if(e == NOMATCH)
cout << "Could not print, ERROR" << endl;
else if(e == EMPTYTREE)
cout << "Database Empty, could not print." << endl;
else if(e == DUPLICATE)
cout << "Could not print, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not print, ERROR" << endl;
cout << endl;
}
}
else if(action == "GRADE")
{
cin >> number;
cin.ignore();
cin >> grade;
cin.ignore();
getline(cin, name);
try
{
t.grade(number, grade, name);
cout << "Set " << name << "'s grade on test " << number << " to " << grade << "." << endl;
cout << endl;
}
catch(int e)
{
if(e == NOMATCH)
cout << "Could not grade " << name << ", no match in database." << endl;
else if(e == EMPTYTREE)
cout << "Could not grade " << name << ", database empty" << endl;
else if(e == DUPLICATE)
cout << "Could not grade, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not grade " << name << ", test number out of range" << endl;
cout << endl;
}
}
else if(action == "DELETE")
{
getline(cin, name);
try
{
t.del(name);
cout << "Successfully deleted " << name << "." << endl;
cout << endl;
}
catch(int e)
{
if(e == NOMATCH)
cout << "Could not delete " << name << ", no match in database." << endl;
else if(e == EMPTYTREE)
cout << "Could not delete " << name << ", database empty" << endl;
else if(e == DUPLICATE)
cout << "Could not delete, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not delete " << name << ", test number out of range ERROR" << endl;
cout << endl;
}
}
else if(action == "MEAN")
{
cin >> number;
try
{
double mean = t.mean(number);
if(mean != 0)
cout << "The mean on test " << number << " is " << t.mean(number) << endl;
else
cout << "There are no nonzero means in the database for test " << number << endl;
cout << endl;
}
catch(int e)
{
if(e == NOMATCH)
cout << "Could not get mean for test " << number << ", no match in database ERROR" << endl;
else if(e == EMPTYTREE)
cout << "Could not get mean for test " << number << ", database empty" << endl;
else if(e == DUPLICATE)
cout << "Could not get mean, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not get mean for test " << number << ", test number out of range." << endl;
else if(e == NONONZERO)
cout << "Could not get mean for test " << number << ", no nonzero grades in database." << endl;
cout << endl;
}
}
}
cout << "Bye, thanks for using." << endl;
}
(c) 2008. CSS: Free CSS Templates.
#:
--- "Do that which consists in taking no action": Lao Tzu