AVL Tree deletion issues
Nov 15, 2014 at 10:51pm UTC
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.