C++

Forum

 
AVL Tree crash bug

Bill Horstkamp (2)
Hey, I am trying to get an AVL Tree working but I seem to be having a problem after running the remove operation several thousand times on a very large tree, causing it to crash. The test file I am using has 100k numbers inserted in random order, then tests the tree by removing the 100k numbers in a different random order, it crashes at the same place every time.
Where have I gone wrong?

Removal and balance code below.

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
 
void AVLTree::remove(int x)
{
	remove(x, root);
}

void AVLTree::remove(int x,Node*& p)
{
	Node* d;
	if (p==NULL)
	{
		cout<<"Sorry! data not found\n"<<endl;
	}
	else if ( x < p->data)
	{
		remove(x,p->left);
		balanceup(p);
	}
	else if (x > p->data)
	{
		remove(x,p->right);
		balanceup(p);
	}
	else if ((p->left == NULL) && (p->right == NULL))
	{
		d=p;
		delete d;
		p=NULL;
	}
	else if (p->left == NULL)
	{
		d=p;
		p=p->right;
		delete d;
		balanceup(p);
	}
	else if (p->right == NULL)
	{
		d=p;
		p=p->left;
		delete d;
		balanceup(p);
	}
	else
	{	
		Node*& m = getMax(p->left);
		p->data = m->data;
		remove(m->data, m);
		balanceup(p);
	}
}

void AVLTree::balanceup(Node*& p)
{
	if ((bsheight(p->left) - bsheight(p->right))==2)
	{
		if ((bsheight(p->left->left) - bsheight(p->left->right)) == 1)
			p = srl(p);
		if ((bsheight(p->left->right) - bsheight(p->left->left)) == 1)
			p = drl(p);
		if ((bsheight(p->left->left) - bsheight(p->left->right)) == 0)
			p = srl(p);
	}
	else if ((bsheight(p->right) - bsheight(p->left))==2)
	{
		if ((bsheight(p->right->left) - bsheight(p->right->right)) == 1)
			p = drr(p);
		if ((bsheight(p->right->right) - bsheight(p->right->left)) == 1)
			p = srr(p);
		if ((bsheight(p->right->left) - bsheight(p->right->right)) == 0)
			p = srr(p);
	}
	else if ((bsheight(p->left) - bsheight(p->right))==1)
		return;
	else if ((bsheight(p->right) - bsheight(p->left))==1)
		return;
	int m,n,d;
	m=bsheight(p->left);
	n=bsheight(p->right);
	d=max(m,n);
	p->height = d + 1;
	if (p->left != NULL)
	{
		m=bsheight(p->left->left);
		n=bsheight(p->left->right);
		d=max(m,n);
		p->left->height = d + 1;
	}
	if (p->right != NULL)
	{
		m=bsheight(p->right->left);
		n=bsheight(p->right->right);
		d=max(m,n);
		p->right->height = d + 1;
	}
}
Bill Horstkamp (2)
Can anyone help me?
height is an int representing the length of the subtree starting with that node as root, bsheight counts how long a subtree is.
Rotation code below:
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
 
Node* AVLTree:: srl(Node*& p1)
{
	Node* p2;
	p2 = p1->left;
	p1->left = p2->right;
	p2->right = p1;
	p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
	p2->height = max(bsheight(p2->left),p1->height) + 1;
	return p2;
}

Node* AVLTree:: srr(Node*& p1)
{
	Node* p2;
	p2 = p1->right;
	p1->right = p2->left;
	p2->left = p1;
	p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
	p2->height = max(p1->height,bsheight(p2->right)) + 1;
	return p2;
}

Node* AVLTree:: drl(Node*& p1)
{
	p1->left=srr(p1->left);
	return srl(p1);
}

Node* AVLTree::drr(Node*& p1)
{
	p1->right = srl(p1->right);
	return srr(p1);
}
Last edited on
Topic archived. No new replies allowed.