#ifndef MyDS_H
#define MyDS_H
#include <iostream>
#include <string>
class MyDS {
private:
struct treeNode
{
treeNode* left;
treeNode* right;
int height;
std::string data;
treeNode() {left = NULL; right = NULL;};
treeNode(const std::string &v, treeNode* l, treeNode* r, int h){data = v; left = l; right = r; height = h;};
};
treeNode* root;
void push(const std::string & n, treeNode * & v);
bool search( const std::string& s, treeNode * & tree) ;
public:
MyDS();
~MyDS();
void push(const std::string & n);
void printPreOrder() const;
void preOrder(treeNode* pre) const;
void clear(treeNode* & tree);
void singleRightRotate(treeNode * & n);
void doubleRightRotate(treeNode * & n);
void singleLeftRotate(treeNode * & n);
void doubleLeftRotate(treeNode * & n);
bool search(const std::string & s);
int avlHeight (treeNode * h);
int max(int v1, int v2);
};
MyDS::MyDS()
{
root = NULL;
}
MyDS::~MyDS()
{
clear(root);
}
void MyDS::push(const std::string & n)
{
push(n,root);
}
void MyDS::singleRightRotate(treeNode * & n)
{
treeNode * temp;
temp = n->right;
n->right = temp->left;
temp->left = n;
n = temp;
n->height = max(avlHeight(n->left),avlHeight(n->right)) + 1;
temp->height = max(n->height,avlHeight(temp->right)) + 1;
}
void MyDS::singleLeftRotate(treeNode * & n)
{
treeNode * temp;
temp = n->left;
n->left = temp->right;
temp->right = n;
n = temp;
n->height = max(avlHeight(n->left),avlHeight(n->right)) + 1;
temp->height = max(avlHeight(temp->left),n->height) + 1;
}
void MyDS::doubleRightRotate(treeNode * & n)
{
singleLeftRotate(n->right);
singleRightRotate(n);
}
void MyDS::doubleLeftRotate(treeNode * & n)
{
singleRightRotate(n->left);
singleLeftRotate(n);
}
int MyDS::max(int v1, int v2)
{
return ((v1 > v2) ? v1 : v2);
}
int MyDS::avlHeight(treeNode * h)
{
int n;
if( h == NULL)
{
return -1;
}
else
{
n = h->height;
return n;
}
}
bool MyDS::search(const std::string& s, treeNode *& tree)
{
if(tree == NULL)
{
return false;
}
else if(s < tree->data)
{
return search(s, tree->left);
}
else if(tree->data < s)
{
return search(s, tree->right);
}
else
{
;
}
}
bool MyDS::search(const std::string &x)
{
if (search(x, root)){
return true;
}
else
return false;
}
void MyDS::clear(treeNode* & tree)
{
if(tree != NULL)
{
clear(tree->left);
clear(tree->right);
delete tree;
}
tree = NULL;
}
void MyDS::push(const std::string & n, treeNode* & v)
{
if (v == NULL)
{
v = new treeNode(n , NULL, NULL, 0);
}
else
{
if ( n < v->data)
{
push(n, v->left); // goes to left node
if ((avlHeight(v->left) - avlHeight(v->right))==2)
{
if (n < v->left->data)
{
singleLeftRotate(v);
}
else
{
doubleLeftRotate(v);
}
}
}
else if ( v->data < n)
{
push(n, v->right); // goes to right node
if ((avlHeight(v->right) - avlHeight(v->left))==2)
{
if (n > v->right->data)
{
singleRightRotate(v);
}
else
{
doubleRightRotate(v);
}
}
}
else
{
; // duplicate; do nothing.
}
}
int a,b,c;
a = avlHeight(v->left);
b = avlHeight(v->right);
c = max(a,b);
v->height = c + 1;
}
void MyDS::printPreOrder() const
{
preOrder(root);
}
void MyDS::preOrder(treeNode* pre) const
{
if(pre != NULL)
{
std::cout << " " << pre->data << " ";
preOrder(pre->left);
preOrder(pre->right);
}
}