AVL Tree deletion issues

I've got a working insert that performs rotations correctly, however, when I remove nodes, rotations are occurring but they aren't re-balancing the tree. I was never originally told how to do a node removal for an AVL except for the fact that it was similar to BST implementation. I would appreciate it if someone could determine my error.

This is the remove function, which, when originally called, takes the root node:

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
template<typename T>
void AVL<T>::remove(AVL_Node<T> *&node, const T &searchKey)
{
	if (node == NULL)
		return;
	else if (searchKey < node->mData)
		remove(node->mLeft, searchKey);
	else if (searchKey > node->mData)
		remove(node->mRight, searchKey);
	else
	{
		if ((node->mLeft == NULL) && (node->mRight == NULL))
		{
			AVL_Node<T>* temp = node->mLeft ? node->mLeft : node->mRight;

			if (temp == NULL)
			{
				temp = node;
				node = NULL;
			}
			else 
				node = temp;

			delete temp;
		}
		else
		{
			AVL_Node<T>* temp = minValueNode(node->mRight);

			node->mData = temp->mData;

			remove(node->mRight, searchKey);
		}
	}

	if (node == NULL)
		return;

	node->mHeight = maxHeight(node->mLeft, node->mRight) + 1;

	node->balanceFactor = height(node->mLeft) - height(node->mRight);

	if (node->balanceFactor == 2)
	{
		if (node->mLeft->balanceFactor == 1)
			rotateRight(node);
		else
			rotateLeftRight(node);
	}
	else if (node->balanceFactor == -2)
	{
		if (node->mRight->balanceFactor == -1)
			rotateLeft(node);
		else
			rotateRightLeft(node);
	}

	node->mHeight = maxHeight(node->mLeft, node->mRight) + 1;

	node->balanceFactor = height(node->mLeft) - height(node->mRight);
}


This is the node structure
1
2
3
4
5
6
7
8
9
10
11
12
template <typename T>
struct AVL_Node
{
	T           mData;
	int balanceFactor,
		mHeight;
	AVL_Node<T> *mLeft, *mRight;

	AVL_Node();
	AVL_Node(T data);
	AVL_Node(T data, AVL_Node<T> *left, AVL_Node<T> *right);
};
Topic archived. No new replies allowed.