C++

Forum

 
help with avl tree

mohammedawni (18)
i try to write a code to balance the BST automatically.
first,it works correctly but after few changes i made.
the find_imbalanced_node function breaks down consequently rotation_engine_rotation breaks down
so,please,can anyone help me to find what is the error in my code?
thank you
here is the whole program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
  #include<iostream>
using namespace std;
int new_data;
void space(){cout<<"//////////////////////////////////////////////////////\n";};
////////////////////////////////////node SRUCUTRE//////////////////////////////////////
struct node{
	int data;
	node *left;
	node *right;
	int balance_factor;
	node():data(NULL),left(NULL),right(NULL),balance_factor(NULL){}
};
//////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////AVL tree class ///////////////////////////////////
class BST{
public:
	node *root;
	BST():root(NULL){cout<<"          this is AVL tree.\n\a";}
	void insert(int);
	void preorder(node *);
	void inorder(node *);
	void postorder(node *);
	int height(node *);
	int diff(node *);
	node *rotateright(node *);
	node *rotateleft(node *);
	node *rotateleftright(node *);
	node *rotaterightleft(node *);
	node *find_imbalanced_node(int);
	void rotation_engine(node *node_root);
	bool find(int item,node *node_root);
	void remove(int item);
	bool find(int item,node*& locptr,node*& parent);
	void rest_the_tree()
	{
		while(root!=NULL)
			remove(root->data);
	}
        bool check_if_not_imbalanced()
	{
		if(root->balance_factor==-2||root->balance_factor==-2||find_imbalanced_node(new_data)!=NULL)
			return true;
		else 
			return false;
	}
};
//////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////Height function////////////////////////////////////////
int BST::height(node *temp){
	int h=0;
	if(temp!=NULL){
		int l_height=height(temp->left);
		int r_height=height(temp->right);
		h=max(l_height,r_height)+1;
	}
	return h;
}
//////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////Balance factor function///////////////////////////
int BST::diff(node *temp){return (height(temp->left)-height(temp->right));}
//////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////Rotate left function//////////////////////////////
node *BST::rotateleft(node *p){
	node *q=p->right;
	p->right=q->left;
	q->left=p;
	return q;
}
/////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////rotate right function//////////////////////////
node *BST::rotateright(node *p){
	node *q=p->left;
	p->left=q->right;
	q->right=p;
	return q;
}
///////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////Rotate left right fun///////////////////////////
node *BST::rotateleftright(node *p)
{
	
	p->left=rotateleft(p->left);
	p=rotateright(p);
	return p;
}
////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////rotate right left fun///////////////////////////////
node *BST::rotaterightleft(node *p)
{
	p->right=rotateright(p->right);
	p=rotateleft(p);
	return p;
}
////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////preorder function///////////////////////////////////
void BST::preorder(node* root_node)
	{
		if(root_node!=NULL)
		{
			root_node->balance_factor=diff(root_node);
			cout<<"Data= "<<root_node->data<<",balance factor = "<<root_node->balance_factor<<endl;
			preorder(root_node->left);
			preorder(root_node->right);
		}

	}
/////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////Insert fuction////////////////////////////////////
void BST::insert(int item)
{
	node* parent=NULL;
    node* locptr=root;
	bool found=false;
	while(!found&&locptr!=NULL)
	{
		parent=locptr;
		if(item<locptr->data)
			locptr=locptr->left;
		else if(item>locptr->data)
			locptr=locptr->right;
		else
			found=true;
	}
	if(!found)
	{
		locptr=new node;
		locptr->data=item;
		if(parent==NULL)
			root=locptr;
		else if(item<parent->data)
			parent->left=locptr;
		else
			parent->right=locptr;
	}else
		cout<<"Item already in the tree\a\n";
}
//////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////find_imbalanced_node function//////////////////////////////
node *BST::find_imbalanced_node(int item)
{
	node *locptr=root;
	node *imbalanced_node=root;
	bool found=false;
	while(!found && locptr!=NULL)
	{
		if(item<locptr->data){
			if(locptr->left->balance_factor==2||locptr->left->balance_factor==-2)imbalanced_node=locptr;
			locptr=locptr->left;
		}
		else if(item>locptr->data){
			if(locptr->right->balance_factor==2||locptr->right->balance_factor==-2)imbalanced_node=locptr;
			locptr=locptr->right;
		}
		else
			found=true;
	}
	if(imbalanced_node==root)imbalanced_node=NULL;
	return imbalanced_node;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
Last edited on
mohammedawni (18)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
 
///////////////////////////////////////////////////////////////////////////////////////////////////////
void BST::rotation_engine(node *node_root)
{
	
	if(node_root != NULL)
	{
		if((node_root->balance_factor==2||node_root->balance_factor==-2)&&find_imbalanced_node(new_data)== NULL)
		{
			if(find(new_data,node_root->right->right))
			{
				cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( left rotation )now....please wait\n ";
				node_root=rotateleft(node_root);
				cout<<"now this tree is an( AVL TREE )\a\n";

			}
			else if(find(new_data,node_root->right->left))
			{
				cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( right left rotation )now....please wait\n ";
				node_root=rotaterightleft(node_root);
				cout<<"now this tree is an( AVL TREE )\a\n";
			}
			else if(find(new_data,node_root->left->left))
			{
				cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( right rotation )now....please wait\n ";
				node_root=rotateright(node_root);
				cout<<"now this tree is an( AVL TREE )\a\n";
			}
			else
			{
				cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( left right rotation )now....please wait\n ";
				node_root=rotateleftright(node_root);
				cout<<"now this tree is an( AVL TREE )\a\n";
			}
			return ;
		}
		if(node_root==find_imbalanced_node(new_data))
		{
			if(find(new_data,node_root->right->left->right))
			{
				cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( left right rotation )now....please wait\n ";
				node_root->left=rotateleftright(node_root->left);
				cout<<"now this tree is an( AVL TREE )\a\n";
			}
			else if(find(new_data,node_root->right->left->left))
			{
				cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( right rotation )now....please wait\n ";
				node_root->right=rotateright(node_root->right);
				cout<<"now this tree is an( AVL TREE )\a\n";
			}
			else if(find(new_data,node_root->right->right->right))
			{
				cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( left rotation )now....please wait\n ";
				node_root->left=rotateleft(node_root->left);
				cout<<"now this tree is an( AVL TREE )\a\n";

			}
			else if(find(new_data,node_root->right->right->left))
			{
				cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( right left rotation )now....please wait\n ";
				node_root->left=rotaterightleft(node_root->left);
				cout<<"now this tree is an( AVL TREE )\a\n";
			}
			else if(find(new_data,node_root->left->right->right))
			{
				cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( left rotation )now....please wait\n ";
				node_root->left=rotateleft(node_root->left);
				cout<<"now this tree is an( AVL TREE )\a\n";

			}
			else if(find(new_data,node_root->left->left->left))
			{
			    cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( right rotation )now....please wait\n ";
				node_root->right=rotateright(node_root->right);
				cout<<"now this tree is an( AVL TREE )\a\n";
			}
			else if(find(new_data,node_root->left->right->left))
			{
				cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( right left rotation )now....please wait\n ";
				node_root->left=rotaterightleft(node_root->left);
				cout<<"now this tree is an( AVL TREE )\a\n";

			}
			else 
			{
				cout<<"Warining: insertion item("<<new_data<<") causes an imbalance at the the tree\a\n";
				cout<<"we have to do( left right rotation )now....please wait\n ";
				node_root->left=rotateleftright(node_root->left);
				cout<<"now this tree is an( AVL TREE )\a\n";
			}
			return ;
		}
		rotation_engine(node_root->left);
		rotation_engine(node_root->right);
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////
bool BST::find(int item,node *node_root)
{
	bool found=false;node*locptr=node_root;
	while(!found&&locptr!=NULL)
	{
		if(item<locptr->data)
			locptr=locptr->left;
		else if(item>locptr->data)
			locptr=locptr->right;
		else 
			found=true;
	}
	return found;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////
void BST::remove(int item)
{
	bool found;
	node* x;
	node* parent;
	found=find(item,x,parent);
	if(!found){
		cout<<"Item is not BST\a\n";
		return;}
	if(x->left!=NULL&&x->right!=NULL){
		node* y=x->right;
		parent=x;
		while(y->left!=NULL){parent=y;y=y->left;}
	x->data=y->data;
	x=y;
}
node* z=x->left;
if(z==NULL)
	z=x->right;
if(parent==NULL)
	root=z;
else if(parent->left==x)
	parent->left=z;
else
	parent->right=z;
delete x;
}
/////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
bool BST::find(int item,node*& locptr,node*& parent)
{
	bool found=false;
	locptr=root;
	parent=NULL;
	while(!found&&locptr!=NULL)
	{
		if(item<locptr->data)
		{
			parent=locptr;
			locptr=locptr->left;
		}
		else if(item>locptr->data)
		{
			parent=locptr;
			locptr=locptr->right;
		}
		else
			found=true;
	}
	return found;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////
void showoptions()
{
	cout<<"Click (1)------->To insert data.\n"
		<<"Click (2)------->To display data.\n"<<"Click (3)------->To find data.\n"<<"Click (4)------->To rest the tree\n"
		<<"Click (5)------->To Exit\n";
}
////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////
int main(){

	BST obj;
	showoptions();int option;
	cout<<"Enter your chosie : ";
	cin>>option;
    space();
	do{
	switch(option)
	{
	case 1:{cout<<"Enter data : ";
		cin>>new_data;obj.insert(new_data);
		if(obj.check_if_not_imbalanced())
			obj.rotation_engine(obj.root);
		system("cls");};break;
	case 2:{obj.preorder(obj.root);};break;
	case 3:{ int value;cout<<"Enter data you want to find : ";cin>>value;
		if(obj.find(value,obj.root))
			   cout<<"data ("<<value<<") is founded in the tree\a\n";
		   else 
			   cout<<"data ("<<value<<") is not founded in the tree\a\n";
		   };break;
	case 4:{obj.rest_the_tree();cout<<"All data have been removed\a\n";};break;
	case 5:{system("cls");cout<<"Thank you for using program.\a\n\n\n\n\n\t\t\t\t\t\t\n";};break;
	default:cout<<"ERROR:wrong choise.\a\n";
	}
	if(option==5)break;
	space();
	showoptions();
	cout<<"Enter your chosie : ";cin>>option;
	system("cls");
	}while(option!=5);
	cin.get();
	return 0;
}
Last edited on
Topic archived. No new replies allowed.