AVL Tree Insertion - Implementation

Question

thank you for all the help you guys have offered me throughout the years. Here comes another concern, and as usual any explanations, suggestions, or corrections are welcomed and appreciated!

I'm working on an assignement in C++ for an AVL tree, currently I'm working on insertion, but also need to implement removal, so even though this post is going to be heavy on insertion code, any pointers as to how to implement removal the easiest way to understand with my code would be awesome!

Okay, so I have the following functions to assist me in balance/insertion:

 int AVL :: returnBalance(Node* nodeme)
{
   return (whatisHeight(nodeme->leftbaby) - whatisHeight(nodeme->rightbaby));
}

int AVL :: whatisHeight(Node* localroot)
{
if(localroot == NULL)
{
    return 0;
}else
    return localroot->getHeight();
}

void AVL :: adjustHeight(Node* localroot)
{
if(localroot != NULL)
{
    localroot->height = 1 + max(whatisHeight(localroot->leftbaby), whatisHeight(localroot->rightbaby));
}
}

bool AVL :: contains(Node* nodeme ,int data)
{
if(!nodeme)
{
    return false;
}else
    if(data == nodeme->value)
    {
        return true;
    }
if(data < nodeme->value)
{
    return contains(nodeme->leftbaby,data);
}else
{
    return contains(nodeme->rightbaby,data);
}
}

// Rotation
void AVL :: rotateLeft(Node* localroot)
{
Node * temp = localroot->rightbaby;
localroot->rightbaby = temp->leftbaby;
temp->leftbaby = localroot;
localroot = temp;

adjustHeight(localroot);
adjustHeight(localroot->rightbaby);
adjustHeight(temp);

}

void AVL :: rotateRight(Node* localroot)
{
Node * temp = localroot->leftbaby;
localroot->leftbaby = temp->rightbaby;
temp->rightbaby = localroot;

adjustHeight(localroot);
adjustHeight(localroot->leftbaby);
adjustHeight(temp);

localroot = temp;


}

And my insertion and insertionrecursive functions are written as follows

bool AVL :: add(int data)
{
if(!contains(root, data))
{
    insertRecursive(root,data);
    return true;
}else
{
    return false;
}
}


Node * AVL :: insertRecursive(Node * nodeme, int data)
{

// getting a number ready to print
int num1 = data;
string out1;
   ostringstream convert1;
  convert1 << num1;
  out1 = convert1.str();

 cout << "running recursive insert -- value: " << out1 << endl;

if(root == NULL)
{
    cout << "adding root node" << endl;

    Node * temporary = new Node(data);
    temporary->height = 0;
    root = temporary;
    return root;

}else
    if(nodeme == NULL)
    {
        cout << "adding at local" << endl;
        nodeme = new Node(data);
        nodeme->height = 0;
        return nodeme;
    }else
        if(data < nodeme->value)
        {
            nodeme->leftbaby = insertRecursive(nodeme->leftbaby,data);

            // balancing and stuff
            adjustHeight(nodeme);
            if ((returnBalance(nodeme) == -2 )&& (returnBalance(nodeme->leftbaby) == -1))
            {
                cout << "rotating right" << endl;
                rotateRight(nodeme);
            }else
            if((returnBalance(nodeme) == -2) && (returnBalance(nodeme->leftbaby) == 1))
            {
                cout << "rotating left ---- 1" << endl;
                rotateLeft(nodeme->leftbaby);
                cout << "rotating right" << endl;
                rotateRight(nodeme);
            }else
                if((returnBalance(nodeme) == 2) && (returnBalance(nodeme->leftbaby) == 1))
                {
                    cout << "rotating left" << endl;
                    rotateLeft(nodeme);
                }
            else
                if((returnBalance(nodeme) == 2) && (returnBalance(nodeme->leftbaby) == -1))
                {
                    cout << "rotating right --- 2" << endl;
                    rotateRight(nodeme->leftbaby);
                    cout << "rotating left" << endl;
                    rotateLeft(nodeme);
                }
            adjustHeight(nodeme);

            //
            return nodeme;
        }
        else
        {

            nodeme->rightbaby = insertRecursive(nodeme->rightbaby,data);


            // balancing and stuff
            adjustHeight(nodeme);
            if ((returnBalance(nodeme) == -2 )&& (returnBalance(nodeme->leftbaby) == -1))
            {
                cout << "rotating right" << endl;
                rotateRight(nodeme);
            }else
                if((returnBalance(nodeme) == -2) && (returnBalance(nodeme->leftbaby) == 1))
                {
                    cout << "rotating left --- 3" << endl;
                    rotateLeft(nodeme->leftbaby);
                    cout << "rotating right" << endl;
                    rotateRight(nodeme);
                }else
                    if((returnBalance(nodeme) == 2) && (returnBalance(nodeme->leftbaby) == 1))
                    {
                        cout << "rotating left" << endl;
                        rotateLeft(nodeme);
                    }
                    else
                        if((returnBalance(nodeme) == 2) && (returnBalance(nodeme-    >leftbaby) == -1))
                        {
                            cout << "rotating right --- 4" << endl;
                            rotateRight(nodeme->leftbaby);
                            cout << "rotating left" << endl;
                            rotateLeft(nodeme);
                        }
            cout << "adjust height" << endl;
            adjustHeight(nodeme);

            //


            return nodeme;
        }
}

the cout s are simply for testing, my classes uses a given test driver, and as it turns out my tree isn't matching what it should when adding 0,1,2,3 to 9. It fails when it adds the 2. Note repeated values are not allowed in this tree, hence the contains function.

Now, In my mind I'm adding to a tree, updating the height, checking the balance and then rotating before I continue, so in my mind I'm keeping my tree balanced as I go. Obviously this isn't implementing correctly, so I need some direction!

Expected tree is:

0 1 0 0 1 2

I'm returning

0 0 1 1 11 2

I apologize to through so much code out there, and I'm sure there aren't many that really want to read it all, but just glancing at it your probably wanting to vomit and can offer a great explanation.

Thank you much! -MJ

Answer 1

in rotation:

localroot = temp;

You should pass parameter by reference. If not, the actual parameter can't be changed and you'll get memory leak.

---

And so does nodeme in AVL :: insertRecursive.