views:

39

answers:

0

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.