#include <iostream>
#include <math.h>
using namespace std;
struct node {
int key;
int balance;
node *right;
node *left;
};
struct stack_elem{
node *vert;
char pos;
//stack_elem* next;
} stack[100];
int stack_len=0;
int imax(int a, int b)
{
return (b<a)?a:b;
}
void SmallRightRotation(node *&a)
{
node *b;
int val_a, val_b, h_P, h_Q, h_R;
b=a->right;
val_a=a->key;
val_b=b->key;
h_Q=0;
h_R=b->balance;
h_P=(imax(h_Q, h_R)+1)-a->balance;
a->key=val_b;
b->key=val_a;
a->right=b->right;
b->right=b->left;
b->left=a->left;
a->left=b;
b->balance=h_Q-h_P;
a->balance=h_R-(imax(h_P, h_Q)+1);
}
void BigRightRotation(node *&a)
{
node *b, *c;
int val_a, val_b, val_c, h_P, h_Q, h_R, h_S;
b=a->right;
c=b->left;
val_a=a->key;
val_b=b->key;
val_c=c->key;
h_Q=0;
h_R=c->balance;
h_S=(imax(h_Q, h_R)+1)+b->balance;
h_P=1+imax(h_S, h_S-b->balance)-a->balance;
a->key=val_c;
c->key=val_a;
b->left=c->right;
c->right=c->left;
c->left=a->left;
a->left=c;
b->balance=h_S-h_R;
c->balance=h_Q-h_P;
a->balance=imax(h_S, h_R)-max(h_P, h_Q);
}
void SmallLeftRotation(node *&a)
{
swap(a->key, a->left->key);
node* L=a->left->left;
a->left->left=a->left->right;
a->left->right=a->right;
a->right=a->left;
a->left=L;
a->balance=1+a->right->balance;
a->right->balance=-1-a->right->balance;
}
void BigLeftRotation(node *&a)
{
swap(a->left->right->key, a->key);
node* M=a->left->right->left;
a->left->right->left=a->left->right->right;
a->left->right->right=a->right;
a->right=a->left->right;
a->left->right=M;
a->balance=0;
a->left->balance=-(a->right->balance==1);
a->right->balance=(a->right->balance==-1);
}
void tree_balance(node *&a, int &cur_balance)
{
node *b;
if (a->balance==2)
{
b=a->right;
if (b->balance==-1)
{
BigRightRotation(a);
cur_balance=-1;
}
else
{
if (b->balance==0)
{
SmallRightRotation(a);
cur_balance=0;
}
else
{
SmallRightRotation(a);
cur_balance=-1;
}
}
}
else
{
if (a->balance==-2)
{
b=a->left;
if (b->balance==1)
{
BigLeftRotation(a);
cur_balance=-1;
}
else
{
if (b->balance==0)
{
SmallLeftRotation(a);
cur_balance=0;
}
else
{
SmallLeftRotation(a);
cur_balance=-1;
}
}
}
else
{
cur_balance=0;
}
}
}
void add2(int k, node *&start)
{
node *newnode, *current;
stack_len=0;
int delta=0;
int change=0;
int newdelta=0;
if (start==NULL)
{
start=new node;
start->key=k;
start->left=NULL;
start->right=NULL;
start->balance=0;
}
else
{
current=start;
while ((k>current->key && current->right!=NULL) || (k<current->key && current->left!=NULL))
{
if (k>current->key)
{
stack[stack_len].pos='r';
stack[stack_len++].vert=current;
current=current->right;
}
else
{
stack[stack_len].pos='l';
stack[stack_len++].vert=current;
current=current->left;
}
}
if (k!=current->key)
{
newnode=new node;
newnode->balance=0;
newnode->key=k;
newnode->left=NULL;
newnode->right=NULL;
if (k>current->key)
{
stack[stack_len].vert=current;
stack[stack_len++].pos='r';
current->right=newnode;
}
else
{
stack[stack_len].vert=current;
stack[stack_len++].pos='l';
current->left=newnode;
}
delta=1;
while (delta!=0 && stack_len!=0)
{
if (stack[stack_len-1].pos=='l')
{
if (stack[stack_len-1].vert->balance==1) change=0;
else change=1;
stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance-1;
}
else
{
if (stack[stack_len-1].vert->balance==-1) change=0;
else change=1;
stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance++;
}
tree_balance(stack[stack_len-1].vert, newdelta);
delta=change+newdelta;
stack_len--;
}
}
}
}
void add(node *&start, int key)
{
if (start->key<key)
if (start->left!=NULL) add(start->left, key);
else
{
start->left=new node;
start->left->key=key;
start->left->right=NULL;
start->left->left=NULL;
}
else
if (start->right!=NULL) add(start->right, key);
else
{
start->right=new node;
start->right->key=key;
start->right->right=NULL;
start->right->left=NULL;
}
}
node* search(node *start, int k, int &depth)
{
if (start==NULL) return NULL;
else
{
if (start->key==k) return start;
if (start->key<k)
{
depth++;
search(start->right, k, depth);
}
else
{
depth++;
search(start->left, k, depth);
}
}
}
bool remove(int k, node *&start)
{
node *cur2, *current;
stack_len=0;
int delta=0;
int change=0;
int newdelta=0;
int temp=0;
if (start==NULL || search(start, k, temp)==NULL) return false;
else
{
current=start;
while ((k>current->key && current->right!=NULL) || (k<current->key && current->left!=NULL))
{
if (k>current->key)
{
stack[stack_len].pos='r';
stack[stack_len++].vert=current;
current=current->right;
}
else
{
stack[stack_len].pos='l';
stack[stack_len++].vert=current;
current=current->left;
}
}
if (k==current->key)
{
if (current->left!=NULL && current->right!=NULL)
{
stack[stack_len].vert=current;
stack[stack_len++].pos='r';
cur2=current->right;
while (cur2->left!=NULL)
{
stack[stack_len].vert=cur2;
stack[stack_len++].pos='l';
cur2=cur2->left;
}
current->key=cur2->key;
if (stack[stack_len-1].vert!=current) stack[stack_len-1].vert->left=cur2->right;
else stack[stack_len-1].vert->right=cur2->right;
delete cur2;
}
else
{
if (current->left==NULL)
{
if (stack_len!=0)
{
if (stack[stack_len-1].pos=='l') stack[stack_len-1].vert->left=current->right;
else stack[stack_len-1].vert->right=current->right;
}
else start=current->right;
}
if (current->right==NULL)
{
if (stack_len!=0)
{
if (stack[stack_len-1].pos=='l') stack[stack_len-1].vert->left=current->left;
else stack[stack_len-1].vert->right=current->left;
}
else start=current->left;
}
delete current;
}
delta=-1;
while (delta!=0 && stack_len!=0)
{
if (stack[stack_len-1].pos=='l')
{
if (stack[stack_len-1].vert->balance==-1) change=-1;
else change=0;
stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance+1;
}
else
{
if (stack[stack_len-1].vert->balance==1) change=-1;
else change=0;
stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance-1;
}
tree_balance(stack[stack_len-1].vert, newdelta);
delta=change+newdelta;
stack_len--;
}
}
}
return true;
}
void prefix(node *start, double &sum, int &n)
{
if (start!=NULL)
{
cout<<start->key<<" ";
sum*=start->key;
n++;
prefix(start->left, sum, n);
prefix(start->right, sum, n);
}
}
int main()
{
node *root, *cur;
root=NULL;
int data=0;
double proizv;
float res;
int steps=0;
int choice=0;
while (choice!=5)
{
cout<<"Enter number of action:"<<endl;
cout<<"1. Add."<<endl
<<"2. Search."<<endl
<<"3. Delete."<<endl
<<"4. Calculate."<<endl
<<"5. Exit."<<endl;
cin>>choice;
switch (choice)
{
case 1:
{
cout<<"Enter data: ";
cin>>data;
add2(data, root);
break;
}
case 2:
{
cout<<"Enter key to search: ";
cin>>data;
cur=search(root, data, steps);
cout<<"Element "<<cur->key<<" founded after "<<steps<<" steps"<<endl;
steps=0;
break;
}
case 3:
{
cout<<"Enter key to delete: ";
cin>>data;
if (remove(data, root)==true) cout<<"Removing is succesfull!"<<endl;
else cout<<"Can't delete!"<<endl;
break;
}
case 4:
{
proizv=1;
steps=0;
cout<<"Path: ";
prefix(root, proizv, steps);
cout<<endl<<"Result: "<<exp(log(proizv)/steps)<<endl;
}
default: cout<<"Invalid number!"<<endl;
}
}
return 0;
}