#include

#include "tree.h"

int change = 0;

int first = 0;

int count1 = 0;

void main(void)

{

std::string s = "fahd";

std::string w = "f";

int q = s==w;

// cout<

keytype i,node;

char choice;

ptrtype a;

treeitemtype x,lson,rson;

bool success = true;

bstclass tree;

ifstream file("data.txt");

for(;;)

{

file>>i;

tree.SearchTreeInsert(i,success);

if( file.eof() )

break;

}

cout<

cout<<"Balance of root before changing "<

//a = tree.give_ptr( 5,tree.getroot(), s

// uccess );

for(;;)

{

cout<

cin>>choice;

if( choice == '0' )

break;

else if( choice == 'd' )

{

cout<

cin>>node;

if(node==0)

break;

tree.SearchTreeDelete( node, success );

count1 = 0;

if( !success )

{

cout<<" ERRORelement not found"<

continue;

}

else if( choice == 'q' )

{

cout<

cin>>node;

if(node==0)

break;

lson.key = 0;

rson.key = 0;

tree.get_sons( node,lson,rson,success);

if( success )

{

if( rson.key == lson.key )

cout<<" Leaf Node "<

else

{

cout<<"Left son"<

cout<<"Right son"<

lson.key = 0;

rson.key = 0;

}

else

{

cout<<"\tNode not Found "<

}

//tree.DeleteRootItem( a );

//a = tree.give_ptr( 6,tree.getroot(), success );

/*tree.SearchTreeDelete( 6, success );

if( !success )

{

cout<<" ERRORelement not found"<

exit(0);

}

//tree.DeleteRootItem( a );

cout<<"Balance of root after balancing "<

tree.get_sons( 7,lson,rson,success);

cout<<"Left son"<

cout<<"Right son"<

}

//**************************************

// *******

tree.h

#include

//////////////////*********************/

/////////////////

//std::string keytype = "fahd";

//typedef std::string keytype;

typedef float keytype;

#define LEFT 1

#define RIGHT 2

////////////////////////////////////////

/////////////////

//**************************************

// *****************

struct dataitem

{

keytype key;

dataitem(const keytype x) { key = x; }

dataitem() {}

};

typedef dataitem treeitemtype;

struct treenode;

typedef treenode *ptrtype;

////////////////////////////////////////

////////////////////

//**************************************

// ********************

////////////////////////////////////////

////////////////////

//**************************************

// ********************

struct treenode

{

treeitemtype item;

ptrtype Lchildptr,Rchildptr;

treenode(treeitemtype x,treenode* y, treenode* z):item(x),Lchildptr(y),Rchildptr(z){}

};

class bstclass

{

public:

bstclass();

bstclass(const bstclass &);

~bstclass();

bool searchtreeisempty();

void SearchTreeInsert(treeitemtype newitem,bool &success);

void DeleteRootItem(ptrtype nodeptr);

void DeleteItem(ptrtype &treeptr,keytype searchkey,bool &success);

void RetrieveItem(ptrtype treeptr,keytype searchkey,

treeitemtype &treeitem,bool &success);

void SearchTreeDelete(keytype searchkey,bool&success);

void SearchTreeRetrieve(keytype searchkey,treeitemtype &search,

bool success);

ptrtype getroot() { return root; }

void setroot(ptrtype ptr) { root = ptr; }

void left_rotation( ptrtype ptr );

void right_rotation( ptrtype ptr );

void get_sons( treeitemtype item,treeitemtype& lson,treeitemtype& rson,bool& success );

ptrtype father( keytype key, int& side, ptrtype ptr );

void traverse(treeitemtype item,ptrtype ptr,treeitemtype& lson,treeitemtype& rson,bool& success);

ptrtype give_ptr( keytype key,ptrtype ,bool& success );

void balance_tree();

void AVL_balance( bstclass& , ptrtype );

void AVL_balance_on_fly( bstclass& , ptrtype );

int balance( ptrtype ptr );

int height( ptrtype ptr);

protected:

ptrtype InsertItem(ptrtype &treeptr,treeitemtype newitem,bool &success);

ptrtype ProcessLeftmost(ptrtype &ptr,treeitemtype &treeitem);

private:

ptrtype root;

};

/*void bstclass::balance_tree()

{

ptrtype p = root;

ptrtype q = root;

extern int first,change;

for(;;)

{

if( p )

{

AVL_balance( *this,p );

p = p->Lchildptr;

}

if( q )

{

q = q->Rchildptr;

AVL_balance( *this,q );

}

/*p = p->Lchildptr;

if( !p )

break;

AVL_balance( *this,p );

q = q->Rchildptr;

if( !q )

break;

AVL_balance( *this,q );

/*if( root->Lchildptr!=0)

AVL_balance( *this,root->Lchildptr );

if( root->Rchildptr!=0)

AVL_balance( *this,root->Rchildptr );*/

//AVL_balance( *this

/* if(change==0)

break;

else

{

first=0;

change=0;

}

}*/

////////////////////////////////////////

///////////////////

void bstclass::left_rotation( ptrtype ptr )

{

ptrtype q,hold,f1;

int flag = false;

extern int change;

int side1 = 0, fside = 0;

change = 1;

cout<<"LEFT Rotation at "<item.key<

if( ptr == root )

flag = true;// rotation on root

q = ptr->Rchildptr;

hold = q->Lchildptr;

q->Lchildptr = ptr;

ptr->Rchildptr = hold;

f1 = father( ptr->item.key, fside, root );

if(fside == LEFT && !flag)

{

f1->Lchildptr = q;

}

else if(fside == RIGHT && !flag)

{

f1->Rchildptr = q;

}

if(flag)

root = q;

}

void bstclass::right_rotation( ptrtype ptr )

{

ptrtype q,hold,f;

int flag = false;

extern int change;

change = 1;

int side1 = 0,fside = 0;

cout<<"RIGHT Rotation at "<item.key<

if( ptr==root )

flag = true;

q = ptr->Lchildptr;

hold = q->Rchildptr;

q->Rchildptr = ptr;

ptr->Lchildptr = hold;

f = father( ptr->item.key,fside,root );

if(fside == LEFT && !flag)

{

f->Lchildptr = q;

}

else if(fside == RIGHT && !flag)

{

f->Rchildptr = q;

}

if(flag)

root = q;

}

void bstclass::get_sons( treeitemtype item,treeitemtype& lson,treeitemtype& rson,bool& success )

{

success = false;

ptrtype ptr;

ptr = root;

if( ptr == 0 )

{

success = false;

return;

}

if( ptr->item.key == item.key )

{

lson.key = (ptr->Lchildptr)->item.key;

rson.key = (ptr->Rchildptr)->item.key;

success = true;

return;

}

traverse(item,ptr->Lchildptr,lson,rson,success);

if(!success)

traverse(item,ptr->Rchildptr,lson,rson,success);

}

void bstclass::traverse(treeitemtype item,ptrtype ptr,treeitemtype& lson,treeitemtype& rson,bool& success)

{

if( ptr == 0)

{

return;

}

if( ptr->item.key == item.key )

{

success = true;

if(ptr->Lchildptr==0 && ptr->Rchildptr==0)

{

return;

}

if(ptr->Lchildptr!=0)

lson.key = ptr->Lchildptr->item.key;

if(ptr->Rchildptr!=0)

rson.key = ptr->Rchildptr->item.key;

return;

}

else

{

traverse(item,ptr->Lchildptr,lson,rson,success);

traverse(item,ptr->Rchildptr,lson,rson,success);

}

ptrtype bstclass::father( keytype key, int& side, ptrtype ptr )

{

ptrtype f;

if( ptr == 0 ) // ptr is the root

return 0;

if( ptr->Lchildptr!=0 && ptr->Lchildptr->item.key == key )

{

side = LEFT;

return ptr;

}

else if( ptr->Rchildptr!=0 && ptr->Rchildptr->item.key == key )

{

side = RIGHT;

return ptr;

}

else

{

if((f = father( key,side,ptr->Lchildptr )) == 0)

return (father( key,side,ptr->Rchildptr ));

else

return f;

}

ptrtype bstclass::give_ptr( keytype key,ptrtype ptr,bool& success )

{

//ptrtype ptr;

ptrtype q,q1;

if( ptr == 0 )

{

success = false;

return 0;

}

if( ptr->item.key == key )

{

return ptr;

}

else

{

q = ptr->Lchildptr;

q = give_ptr( key,q, success );

if( q!=0 )

{

success = true;

return q;

}

q1 = ptr->Rchildptr;

q1 = give_ptr( key,q1,success );

if( q!=0 )

{

success = true;

return q;

}

//**************************************

// ******************

void bstclass::AVL_balance_on_fly( bstclass& tree , ptrtype ptr )

{ // first time it accepts the Rchild of the node

int empty = 2;

//static int count = 0;

extern int count1;

if( ptr == 0 )

return;

// this condition will always be true fo

// r insertion and so oit will not proceed

// any further

if( ptr->Lchildptr == 0 && ptr->Rchildptr == 0 )

{

AVL_balance( tree, ptr );

return;

}

////////////

if( ptr->Lchildptr == 0 && ptr->Rchildptr!=0)

{

AVL_balance( tree, ptr );

return;

}

/*else if( ptr->Rchildptr == 0 && ptr->Lchildptr!=0 )//&& ptr->Lchildptr!=0 )

{

AVL_balance_on_fly( tree, ptr->Lchildptr );

return;

}*/

else if( count1 == 0 && ptr->Rchildptr!=0 )

{

count1++;

AVL_balance_on_fly( tree, ptr->Rchildptr );

}

else

AVL_balance_on_fly( tree, ptr->Lchildptr );

/* else if( ptr->Lchildptr == 0 && ptr->Rchildptr!=0 )

{

empty = LEFT;

}

else if( ptr->Rchildptr == 0 && ptr->Lchildptr!=0 )

{

empty = RIGHT;

}

else if( ptr->Lchildptr == 0 && ptr->Rchildptr == 0 )

{

AVL_balance( tree, ptr );

return;

}

**/

/* if( empty!=LEFT )

AVL_balance_on_fly( tree, ptr->Lchildptr );

if( empty!=RIGHT )

AVL_balance_on_fly( tree, ptr->Rchildptr );*/

}

// function AVL_BALANCE

void bstclass::AVL_balance( bstclass& tree, ptrtype ptr )

{

int n,x;

int fside;

n = balance( ptr );

if( n==2 )

{

x = balance(ptr->Lchildptr);

if(x>=0) // case 1

{

right_rotation( ptr ); // ptr is the node to be rotated

return;

}

else if( x<0 ) // case 3

{

left_rotation( ptr->Lchildptr );

right_rotation( ptr );

return;

}

else if( n==-2 )

{

// check the balance of its son ( right )

x = balance( ptr->Rchildptr );

if( x<=0 ) // case 2

{

//case 2

left_rotation( ptr );

return;

}

else if( x>0 ) // case 2

{

// case 4

right_rotation( ptr->Rchildptr);

left_rotation( ptr);

return;

}

/* if( ptr->Lchildptr!=0 )

AVL_balance( tree, ptr->Lchildptr );

if( ptr->Rchildptr!=0 )

AVL_balance( tree, ptr->Rchildptr );

/**/

if( ptr == root )

return;

ptrtype f = father( ptr->item.key, fside, root );

AVL_balance( tree, f );

}

int bstclass::balance( ptrtype ptr )

{

int Hl = 0;

int Hr = 0;

if( ptr == 0 )

goto label;;

Hl = height(ptr->Lchildptr);

Hr = height(ptr->Rchildptr);

label:

return (Hl-Hr);

}

int bstclass::height( ptrtype ptr)

{

int L=0,R=0;

if( ptr == 0 )

return 0;

L = height(ptr->Lchildptr);

R = height(ptr->Rchildptr);

if(L>R)

return L+1;

else

return R+1;

}

////////////////////////////////////////

///////////////////

bstclass::bstclass():root(NULL)

{

}

bstclass::bstclass(const bstclass &T)

{

// copytree(T.root,root);

}

bstclass::~bstclass()

{

// destroytree(root);

}

bool bstclass::searchtreeisempty()

{

return(root==NULL);

}

void bstclass::SearchTreeInsert(treeitemtype newitem,bool &success)

{

ptrtype ptr;

ptr = InsertItem(root,newitem,success);

//AVL_balance_on_fly( *this,ptr );

AVL_balance(*this,ptr);

}

void bstclass::SearchTreeDelete(keytype searchkey,bool&success)

{

DeleteItem(root,searchkey,success);

}

void bstclass::SearchTreeRetrieve(keytype searchkey,treeitemtype &record,/* search*/

bool success)

{

RetrieveItem(root,searchkey,record,success);

}

ptrtype bstclass::InsertItem(ptrtype &treeptr,treeitemtype newitem,bool &success)

{

if(treeptr==NULL)

{

treeptr=new treenode(newitem,NULL,NULL);

assert(treeptr!=NULL);// success removed

return treeptr;

}

else if(newitem.keyitem.key)

{

InsertItem(treeptr->Lchildptr,newitem,success);

}

else

{

InsertItem(treeptr->Rchildptr,newitem,success);

}

ptrtype bstclass::ProcessLeftmost(ptrtype &ptr,treeitemtype &treeitem)