C++ AVLTree Rotation

Question

I'm trying to do a LeftRotation with my AVLTree. I'll insert 3, 5, and then 10 so it becomes a degenerate tree. When I traverse it'll give me 3, 5, 10 but when I do the rotation I just get 5, 10 instead of the expected 5, 3, 10.

It's something to do with setting a as b's left branch. I will step through it and the root of my tree will be 5, the left will be 3, and the right will be 10, but when I go to traverse it shows the left side as being null.

Here is my rotation code:

void AVLTree::RotateLeft(Node *root)
{
    Node a = *root;
    Node b = *root->GetRight();
    *root = b;
    a.SetRight(b.GetLeft());
    b.SetLeft(&a); //This is where the problem occurs
}

And my Traversal code:

void AVLTree::Traverse(Node *node)
{
    cout << node->GetValue() << ", ";
    if (node->GetLeft() != nullptr)
        Traverse(node->GetLeft());
    if (node->GetRight() != nullptr)
        Traverse(node->GetRight());
}

Thanks in advance!

Edit: changed all 0's to nullptr, thanks for the correction!

Answer 1

There is a problem with how root is moved to point to a new location. If there are doubts about that, consider the following two statements. Note that the variable naming convention from the original code above is used for consistency.

*root = b; // (1)
root = &b; // (2)

In (1), the contents of the root pointer are modified to contain the value stored in the b variable. The address of root has not been modified in any way. The address root has prior to (1) executing remains unchanged after (1) is finished.

In (2), root is now pointing to the address of the b variable. Because the address where root is pointing has been modified, the contents of the root pointer now equal the value in the b variable.

I strongly recommend stepping through the void AVLTree::RotateLeft(Node *root) function line by line and inspecting all variables' addresses and contents to see this first hand. I have performed a simulation of the above actions on sample integer data and pointers moved around as expected using (2).

Before the rotation occurs on the sample data, it is expected that the unbalanced tree should be arranged such that the 3 node is pointed to by root. Then root->right points to 5, and the root->right->right points to 10. The root->right->left should be nullptr, and the root->left should also be nullptr.

If this not the case, then either the AVL insertion algorithm is implemented incorrectly or the design requirements are different than expected (e.g. AVL tree on Wikipedia, Data Structures and Algorithm Analysis in C++ (3rd Edition) [Hardcover] by Mark Allen Weiss, AVL Tree Tutorial on Eternally Confuzzled by Julienne Walker).

Regarding the movement of balancing the tree, where the end result is root points to 5, the root->left points to 3 and root->right points to 10, the right pointer of the passed in root pointer will be set to point to the left pointer of the local pB pointer (see below), the left pointer of pB will point to the passed in root pointer, and root will be set to point to the local variable pB (originally set to the root->right pointer in this case).

Using the sample data above, the body of the function is modified. Note that this is not consistent with how GetRight() and GetLeft() appear to return a Node copy in the original post above. The modified function body below is consistent with the single AVL rotation with right child implemented by Mark Allen Weiss referenced above. Since the original post does not have a height variable, the code below does not either.

//
// The `root` variable is passed as a pointer by reference
//
void AVLTree::RotateLeft(Node* & root)
{
    //
    // This works as long as the GetRight() method returns a pointer, not a Node copy
    //
    Node *pB = root->GetRight();

    //
    // In the example values for three nodes, the root->right will become nullptr
    //
    root->SetRight(pB->GetLeft());

    //
    // In the example values, the pB->left will point to the node with value of 3
    //
    pB->SetLeft(root);

    //
    // Move root to point to where pB does (root->right)
    //
    root = pB;
}