I've run in to an issue with the balance part of my tree. I have checkBal called after a recursive insertion. If I try to add 5, 2 and 4 it checks the balance of 2 and continues back up to 5 then goes into rotateLeft part of the right rotate which is correct. But the rotateLeft function errors on the second line.
What is wrong with this implementation? I've searched all over and compared what I did to the way people talk about how it's done. I finally got everything working. I was forgetting to set N to K at the end.
//==============================================================================
//===== Set Balance ============================================================
sNode<T>* checkBal(sNode<T> *locRoot)
{
// Make sure to check the children are balanced as well.
if (locRoot->left != NULL)
locRoot->left = checkBal(locRoot->left);
if (locRoot->right != NULL)
locRoot->right = checkBal(locRoot->right);
if(getHeight(locRoot->left) - getHeight(locRoot->right) > 1)
{
if(getHeight(locRoot->left->right) > getHeight(locRoot->left->left))
locRoot->left = rotateRight(locRoot->left);
locRoot = rotateLeft(locRoot);
}
else if(getHeight(locRoot->right) - getHeight(locRoot->left) > 1)
{
if(getHeight(locRoot->right->left) > getHeight(locRoot->right->right))
locRoot->right = rotateLeft(locRoot->right);
locRoot = rotateRight(locRoot);
}
updateHeights(locRoot);
return locRoot;
}
/*
Extream cases of balancing a tree requires a double rotation
A
\
D
/
B
'A' is the current root
If right->left (grandchild) is larger then the right->right (grandchild)
First Right rotate the child then left rotate the parent
left > right by 2 or more
left.left < left.right (Double Right Rotation)
left.left >= left.right (Single Right Rotation)
right > left by 2 or more
right.right < right.left (Double Left Rotation)
right.right >= right.left (Single Left Rotation)
*/
sNode<T>* rotateRight(sNode<T> *N) const
{
/*
N K
/ \ / \
(a) K => N (c)
/ \ / \
(b) (c) (a) (b)
*/
// K is going to be our new Parent
// Move (c) from K->right to N->left
// Set K->right to be N
// Return the new parent node to update the one above.
sNode<T> *K = N->right;
N->right = K->left;
K->left = N;
return N = K;
}
I got it working after messing around with it a little while. My solution is below.
//==============================================================================
//===== AVL Balance ============================================================
sNode<T>* checkBal(sNode<T> *locRoot)
{
// Go all the way down to the leaf nodes.
if (locRoot->left != NULL)
locRoot->left = checkBal(locRoot->left);
if (locRoot->right != NULL)
locRoot->right = checkBal(locRoot->right);
// Before we do anything lets update the parent/child heights
updateHeights(locRoot);
if(getHeight(locRoot->left) - getHeight(locRoot->right) > 1)
{
// If it needs a double left rotate first rotate the left child right
if(getHeight(locRoot->left->right) > getHeight(locRoot->left->left))
locRoot->left = rotateRight(locRoot->left);
locRoot = rotateLeft(locRoot);
}
else if(getHeight(locRoot->right) - getHeight(locRoot->left) > 1)
{
// If it needs a double right rotate first rotate the right child left
if(getHeight(locRoot->right->left) > getHeight(locRoot->right->right))
locRoot->right = rotateLeft(locRoot->right);
locRoot = rotateRight(locRoot);
}
// Update the new heights
updateHeights(locRoot);
return locRoot;
}
/*
Extream cases of balancing a tree requires a double rotation
A
\
D
/
B
'A' is the current root
If right->left (grandchild) is larger then the right->right (grandchild)
First Right rotate the child then left rotate the parent
left > right by 2 or more
left.left < left.right (Double Right Rotation)
left.left >= left.right (Single Right Rotation)
right > left by 2 or more
right.right < right.left (Double Left Rotation)
right.right >= right.left (Single Left Rotation)
*/
sNode<T>* rotateRight(sNode<T> *N) const
{
/*
N K
/ \ / \
(a) K => N (c)
/ \ / \
(b) (c) (a) (b)
*/
// K is going to be our new Parent
// Move (c) from K->right to N->left
// Set K->right to be N
// Return the new parent node to update the one above.
sNode<T> *K = N->right;
N->right = K->left;
K->left = N;
return N = K;
}
sNode<T>* rotateLeft(sNode<T> *N) const
{
/*
N K
/ \ / \
K (a) => (b) N
/ \ / \
(b) (c) (c) (a)
*/
sNode<T> *K = N->left;
N->left = K->right;
K->right = N;
return N = K;
}