I am trying to implement an AVL tree for educational purposes but the rotation is not working like I expected.
I have nodes which each have a pointer to a left, right and parent node.
Below is my code for the right-right rotation. First the imput (Just so I make it clear, this is what I understand to be the RR case)
a
\
b
\
c
Code to do rotation is
if (subTreeRoot == root) {
this->root=subTreeRoot->right;
}
else { // not resetting at root
subTreeRoot->right->myParent = subTreeRoot->myParent;
subTreeRoot->myParent->right = subTreeRoot->right;
}
subTreeRoot->right->left = subTreeRoot;
subTreeRoot->right = NULL;
subTreeRoot->height = 1;
return;
This actually works. It even works if a is not the root.
The test case that is failing is something like d c b a e
In this case I do the rotate and then come along and stick something else in.
I was going to go back and look at
http://www.cse.ohio-state.edu/~sgomori/570/avlrotations.html
But I wanted to make sure first I wasn't just barely off or else way to far off.