C++

Forum

 
Ideas for implementing AVL tree.

Skynet (66)
I have this code so far and I would like to see if I can't get it running but in AVL format. I have an idea on how AVL trees work and i can do it on paper but doing it here is hard since I'm not sure how to put it to a computer. I know I can use recursion but one problem is the way I want to implement would cause it to crash since I can't call a million recursions since it is not allowed. I wanted to know if you could help me figure out a way to implement the balancing function. I wanted to get it to just work. I wanted to see your ideas, I don't care how it does it, I just want it to do it. Assume I'm so new to this it hurts. I'm still working on this program to work out bugs leading up to the AVL balancing so there are bugs and errors in this code but I'm working on them right now.

This is what I have coded so far.

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
 
#include <iostream>
#include "binarySearchTree.h"
using namespace std;

int main()
{

	binarySearchTree tree;

	tree.insert(53);
	tree.insert(11);
	tree.insert(98);
	tree.insert(74);
	tree.insert(7);
	tree.insert(5);
	tree.insert(48);
	tree.insert(2);
	tree.insert(23);
	tree.insert(100);
	tree.insert(63);

	tree.display();

	//tree.height();

	tree.extractmin();
	tree.extractmin();
	tree.extractmin();

	tree.remove(63);
	tree.remove(7);
	tree.remove(100);

	return 0;
}


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
 
#include <iostream>
using namespace std;

class binarySearchTree
{
private:
	class node
	{
	public:
		int data;
		int height;
		node * left;
		node * right;

		node(int x)
		{
			data = x;
			left = NULL;
			right = NULL;
		}
	};

	node * root;

	//recursive methods

	int recInsert(int x, node * &r)
	{
		int tmp = 0;
		if( r == NULL )
		{
			r = new node(x);
		}
		else
		{
			if( x < r->data )
			{
				r-> height = recInsert(x, r->left);
			}
			else
			{
				r-> height = recInsert(x, r->right);
			}
		}
		return tmp+1;
	}

	//display items in tree rooted at r
	void recDisplay(node * r)
	{
		if( r != NULL )
		{
			recDisplay(r->left);
			cout << r->data << endl;
			
			cout<<"Height is: " << r->height << endl;

			recDisplay(r->right);
		}
	}
	//	int getHeight( node * r )
	//{
	//	// Max is the greatest height below (*r), temp is just used to avoid calling getHeight(r->right) twice
	//	int max=0,temp=0;
	//	// Recurse down lhs
	//	if (r->left!=NULL) max=getHeight(r->left);
	//	// Recurse down rhs
	//	if (r->right!=NULL) temp=getHeight(r->right);
	//	if (temp>max) max=temp;

	//	// Return the max
	//	return max+1;
	//}

	//return height of tree rooted at r
	

	int extractMin(node * &r)
	{
		int num=0;
		node *min = NULL;
		node *tmp = NULL;
		min = r;
		// Recurse down lhs
		while (min->left!=NULL) 
		{
			tmp = min;
			min = min->left;
		}

		tmp->left = NULL;

		if (r->right!=NULL)
			tmp->left = min->right;

		num = min->data;
		delete min;

		return num;

	}

	int extract(int a, node * &r)
	{
		int num=0;
		node *min = NULL;
		node *tmp = NULL;
		int temp = 0;
		temp = a;
		min = r;
		if (min->data == a) 
		{
			if (min->right != NULL)
				extractMin(min->right);
			else
				r = r->left;
		}

		else if (min->data < a && min->right != NULL)
		{
			extract(temp, min->right);
		}

		else if(min->data > a && min->left != NULL)
		{
			extract(temp, min->left);
		}

		return temp;
	}

public:

	binarySearchTree()
	{
		root = NULL;
	}

	void insert(int x)
	{
		recInsert(x, root);
	}

	//display all items in tree
	void display()
	{
		recDisplay(root);
	}

	//void height()
	//{
	//	cout<<getHeight(root)<<endl;
	//}

	void extractmin()
	{
		cout<<extractMin(root)<<endl;
	}

	void remove(int z)
	{
		cout<<extract(z, root)<<endl;
	}
};
Deep Raithatha (2)
Some errors and warnings occur during the run!!!
Find the errors and fix them!!!!!
pls!
Splux (81)
Wouldn't it be better if you actually copy and pasted the errors here?

(damn... thought OP and the second poster was the same guy...)
Last edited on
ashutosh jha (6)
#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
int data,height;
node *left,*right;
};
typedef node *nodeptr;
class aj
{
struct node1
{
node *d;
node1 *link;
}*front,*rear;
int i,j;
public:
void enque(nodeptr );
void deque();
void bfs(nodeptr );
aj();
void add(int ,nodeptr &);
int bh(nodeptr );
int max(int ,int );
nodeptr rr(nodeptr );
nodeptr lr(nodeptr );
nodeptr lrr(nodeptr );
nodeptr rlr(nodeptr );
void del(int x,nodeptr &);
};
void aj::del(int x,nodeptr &p)
{
nodeptr d;
if(p==NULL)
cout<<"\nElement not found";
else if(x<p->data)
{
del(x,p->left);
if(bh(p->right)-bh(p->left)==2)
{
if(bh(p->right->right)>=bh(p->right->left))//RR
p=lr(p);
else//RL
p=rlr(p);
}
}
else if(x>p->data)
{
del(x,p->right);
if(bh(p->left)-bh(p->right)==2)
{
if(bh(p->left->left)>=bh(p->left->right))//LL
p=rr(p);
else//LR
p=lrr(p);
}
}
else if(p->left==NULL&&p->right==NULL)
{
d=p;
p=NULL;
delete d;
}
else if(p->left==NULL)
{
d=p;
p=p->right;
delete d;
}
else if(p->right==NULL)
{
d=p;
p=p->left;
delete d;
}
else
{
nodeptr t=p->right,q=p;
while(t->left!=NULL)//inorder successor evaluation
t=t->left;

int k=t->data;

del(k,p);
q->data=k;
}

if(p!=NULL)
{
int d1=max(bh(p->left),bh(p->right));
p->height=d1+1;
}
}
aj::aj()
{
front=NULL;
}
void aj::enque(nodeptr p)
{
node1 *temp=new node1;
temp->d=p;
temp->link=NULL;
if(front==NULL)
front=rear=temp;
else
{
rear->link=temp;
rear=temp;
}
}
void aj::deque()
{
node1 *temp=front;
front=front->link;
delete temp;
}
void aj::bfs(nodeptr p)
{
enque(p);
while(front!=NULL)
{
p=front->d;
deque();
if(p->left!=NULL)
enque(p->left);
if(p->right!=NULL)
enque(p->right);
cout<<endl<<p->data;
}
}
nodeptr aj::rr(nodeptr p)//for LL
{
nodeptr q=p->left;
p->left=q->right;
q->right=p;
p->height=max(bh(p->left),bh(p->right))+1;
q->height=max(bh(q->left),p->height)+1;
return q;
}
nodeptr aj::lrr(nodeptr p)//for LR
{
p->left=lr(p->left);
return rr(p);
}
nodeptr aj::lr(nodeptr p)//for RR
{
nodeptr q=p->right;
p->right=q->left;
q->left=p;
p->height=max(bh(p->left),bh(p->right))+1;
q->height=max(p->height,bh(q->right))+1;
return q;
}
nodeptr aj::rlr(nodeptr p)//for RL
{
p->right=rr(p->right);
return lr(p);
}
void aj::add(int x,nodeptr &p)
{
if(p==NULL)
{
p=new node;
p->data=x;
p->left=p->right=NULL;
}
else
{
if(x<p->data)
{
add(x,p->left);
if((bh(p->left))-(bh(p->right))==2)
{
if(x<p->left->data)//LL
p=rr(p);
else//LR
p=lrr(p);
}
}
else if(x>p->data)
{
add(x,p->right);
if((bh(p->right))-(bh(p->left))==2)
{
if(x>p->right->data)//RR
p=lr(p);
else//RL
p=rlr(p);
}
}
else
cout<<"\nData exist";
}
int m,n,d;
m=bh(p->left);
n=bh(p->right);
d=max(m,n);
p->height=d+1;
}
int aj::bh(nodeptr p)
{
int t;
if(p==NULL)
return -1;
else
{
t=p->height;
return t;
}
}
int aj::max(int v1,int v2)
{
return((v1>v2)?v1:v2);
}
int main()
{
int d;
nodeptr root=NULL;
aj a;
a.add(65,root);
a.add(85,root);
a.add(45,root);
a.add(55,root);
a.add(35,root);
a.add(95,root);
a.add(60,root);
a.add(80,root);
a.add(105,root);
cout<<"\nBfs trav::\n";
a.bfs(root);
cout<<"\nEnter data to delete::";
cin>>d;
a.del(d,root);
cout<<"\nBfs trav after deletion";
a.bfs(root);
system("pause");
return 0;
}


Trry this code....
ashutosh jha (6)
//Another way of deletion in avl
//its easier to understand
#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{
int data,height;
node *left,*right;
};
typedef node *nodeptr;
class aj
{
struct node1
{
node *d;
node1 *link;
}*front,*rear;
int i,j;
public:
void enque(nodeptr );
void deque();
void bfs(nodeptr );
aj();
void add(int ,nodeptr &);
int bh(nodeptr );
int max(int ,int );
void inorder(nodeptr );
nodeptr rr(nodeptr );
nodeptr lr(nodeptr );
nodeptr lrr(nodeptr );
nodeptr rlr(nodeptr );
void del(int x,nodeptr &);
int delmin(nodeptr &);
void setheight(nodeptr &);
void check(nodeptr &);
void set(nodeptr &);
};
void aj::setheight(nodeptr &p)
{
if(p!=NULL)
{
setheight(p->left);
setheight(p->right);
int m,n,d;
m=bh(p->left);
n=bh(p->right);
d=max(m,n);
p->height=d+1;
}
}
void aj::check(nodeptr &p)
{
if(p!=NULL)
{
if(bh(p->left)-bh(p->right)==2||bh(p->right)-bh(p->left)==2)
set(p);
check(p->left);
check(p->right);
}
}
void aj::set(nodeptr &p)
{
if(bh(p->left)-bh(p->right)==2)
{
if(bh(p->left->left)>=bh(p->left->right))//LL
p=rr(p);
else//LR
p=lrr(p);
}
if(bh(p->right)-bh(p->left)==2)
{
if(bh(p->right->right)>=bh(p->right->left))//RR
p=lr(p);
else//RL
p=rlr(p);
}
}
void aj::del(int x,nodeptr &p)
{
nodeptr d;
if(p==NULL)
cout<<"\nElement not found";
else if(x<p->data)
del(x,p->left);
else if(x>p->data)
del(x,p->right);
else if(p->left==NULL&&p->right==NULL)
{
d=p;
p=NULL;
delete d;
}
else if(p->left==NULL)
{
d=p;
p=p->right;
delete d;
}
else if(p->right==NULL)
{
d=p;
p=p->left;
delete d;
}
else
p->data=delmin(p->right);
}
int aj::delmin(nodeptr &p)
{
int d;
nodeptr d1;
if(p->left==NULL)
{
d=p->data;
d1=p;
p=p->right;
delete d1;
}
else
{
d=delmin(p->left);
return d;
}
}
aj::aj()
{
front=NULL;
}
void aj::enque(nodeptr p)
{
node1 *temp=new node1;
temp->d=p;
temp->link=NULL;
if(front==NULL)
front=rear=temp;
else
{
rear->link=temp;
rear=temp;
}
}
void aj::deque()
{
node1 *temp=front;
front=front->link;
delete temp;
}
void aj::bfs(nodeptr p)
{
enque(p);
while(front!=NULL)
{
p=front->d;
deque();
if(p->left!=NULL)
enque(p->left);
if(p->right!=NULL)
enque(p->right);
cout<<endl<<p->data;
}
}
nodeptr aj::rr(nodeptr p)//for LL
{
nodeptr q=p->left;
p->left=q->right;
q->right=p;
p->height=max(bh(p->left),bh(p->right))+1;
q->height=max(bh(q->left),p->height)+1;
return q;
}
nodeptr aj::lrr(nodeptr p)//for LR
{
p->left=lr(p->left);
return rr(p);
}
nodeptr aj::lr(nodeptr p)//for RR
{
nodeptr q=p->right;
p->right=q->left;
q->left=p;
p->height=max(bh(p->left),bh(p->right))+1;
q->height=max(p->height,bh(q->right))+1;
return q;
}
nodeptr aj::rlr(nodeptr p)//for RL
{
p->right=rr(p->right);
return lr(p);
}
void aj::add(int x,nodeptr &p)
{
if(p==NULL)
{
p=new node;
p->data=x;
p->left=p->right=NULL;
}
else
{
if(x<p->data)
{
add(x,p->left);
if((bh(p->left))-(bh(p->right))==2)
{
if(x<p->left->data)//LL
p=rr(p);
else//LR
p=lrr(p);
}
}
else if(x>p->data)
{
add(x,p->right);
if((bh(p->right))-(bh(p->left))==2)
{
if(x>p->right->data)//RR
p=lr(p);
else//RL
p=rlr(p);
}
}
else
cout<<"\nData exist";
}
int m,n,d;
m=bh(p->left);
n=bh(p->right);
d=max(m,n);
p->height=d+1;
}
int aj::bh(nodeptr p)
{
int t;
if(p==NULL)
return -1;
else
{
t=p->height;
return t;
}
}
int aj::max(int v1,int v2)
{
return((v1>v2)?v1:v2);
}
void aj::inorder(nodeptr p)
{
if(p!=NULL)
{
inorder(p->left);
cout<<endl<<p->data;
inorder(p->right);
}
}
int main()
{
int d;
nodeptr root=NULL;
aj a;
a.add(65,root);
a.add(85,root);
a.add(45,root);
a.add(55,root);
a.add(35,root);
a.add(95,root);
a.add(60,root);
cout<<"\nBfs trav::\n";
a.bfs(root);
cout<<"\nEnter data to delete::";
cin>>d;
a.del(d,root);
cout<<"\nBfs trav after deletion";
a.bfs(root);
cout<<"\nBfs trav after balancing tree";
a.setheight(root);
a.check(root);
a.bfs(root);
system("pause");
return 0;
}
Topic archived. No new replies allowed.