C++

Forum

 
AVL Tree Error

natekelsey (97)
I'm getting an error on my getHeightDifference() for my AVL tree. I've included my insert, rebalance, updateHeight, and getHeightDifference functions for people to look. I'm not sure if I have my updateHeight and rebalance in the right locations though. Advice is greatly appreciated. 

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
 
void avlTree::insert(Node*& n, int item)
{
	// If node is null, create a new node with input data
	if(n==nullptr)
	{
		n=new Node(item);
		//n->updateHeight(n);
	}
	else
	{
		// Check to see if data being inserted is < current node->data
		if(item < (n->data))
		{
			// recursive call with left child node input node
			insert((n->left), item);
			//n->updateHeight(n);
			rebalance(n->left);
		}
		// Check to see if data being inserted is > current node->data
		else if(item > (n->data))
		{
			// recursive call with left child node input node
			insert((n->right), item);
			rebalance(n->right);
			//n->updateHeight(n);
		}
		else
			// If item is a duplicate, output duplicate message
			cout<<item<<" is a duplicate"<<endl;
	}
}

void avlTree::rebalance(Node*& n)
{
	n->updateHeight(n);
	int heightDifference=n->getHeightDifference(n);
	// Node n's left subtree is taller than its right subtree by more than 1
	if(heightDifference > 1)
	{ 
		// Addition was in Node n's left subtree
		// Left child of Node n has a left subtree that is taller than
                // its right subtree
		if(n->getHeightDifference(n->left) > 0)
			// Addition was in left subtree of left child
                        n=rotateRight(n);  
		else
                        // Addition was in right subtree of left child
			n=rotateLeftRight(n)	;		
	}
	// Node n's right subtree is taller than its right subtree by less than    
        // -1
	else if(heightDifference < -1)
	{ 
		// Addition was in Node n's right subtree
		// Right child of Node n has a right subtree that is taller 
                // than its left subtree
		if(n->getHeightDifference(n->right) < 0)
                        // Addition was in right subtree of right child
			n=rotateLeft(n);				
		else
                        // Addition was in left subtree of left child
			n=rotateRightLeft(n);		
	}
	else
		return;
}

int Node::getHeightDifference(Node *n)
{
	 return n->left->height - n->right->height;   //ERROR IS HERE.
}

// If anyone knows of a more simplified version of this that would be nice but
// not necessary
void Node::updateHeight(Node *n)
{
	if(n->left == nullptr && n->right == nullptr)
	{
		n->height=1;
		return;
	}
	if(n->left != nullptr)
		updateHeight(n->left);
	if(n->right != nullptr)
		updateHeight(n->right);
	if(n->left != nullptr && n->right != nullptr)
	{
		if(n->left->height > n->right->height)
			n->height=n->left->height+1;
		else
			n->height=n->right->height+1;
	}
	if(n->left != nullptr && n->right == nullptr)
		n->height=n->left->height+1;
	else
		n->height=n->right->height+1;
}
Topic archived. No new replies allowed.