Вставка дерева AVL — реализация

спасибо за всю помощь, которую вы, ребята, предлагали мне на протяжении многих лет. Здесь возникает еще одна проблема, и, как обычно, любые объяснения, предложения или исправления приветствуются и приветствуются!

Я работаю над заданием на С++ для дерева AVL, в настоящее время я работаю над вставкой, но мне также нужно реализовать удаление, поэтому, хотя этот пост будет тяжелым для кода вставки, любые указатели на то, как реализовать удаление самый простой способ понять мой код было бы здорово!

Итак, у меня есть следующие функции, которые помогут мне в балансировке/вставке:

 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;


}

И мои функции вставки и вставки рекурсивные записываются следующим образом

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;
        }
}

cout просто для тестирования, мои классы используют данный тестовый драйвер, и, как оказалось, мое дерево не соответствует тому, что должно при добавлении 0,1,2,3 к 9. Оно терпит неудачу, когда добавляет 2. Обратите внимание, что в этом дереве не допускаются повторяющиеся значения, поэтому функция содержит.

Теперь, мысленно я добавляю дерево, обновляю высоту, проверяю баланс и затем поворачиваю, прежде чем продолжить, так что мысленно сохраняю дерево сбалансированным по мере продвижения. Очевидно, что это работает неправильно, поэтому мне нужно какое-то направление!

Ожидаемое дерево:

0 1 0 0 1 2

я возвращаюсь

0 0 1 1 11 2

Я извиняюсь за то, что написал так много кода, и я уверен, что немногие действительно хотят прочитать все это, но просто взглянув на него, вы, вероятно, захотите блевать и можете предложить отличное объяснение.

Спасибо много! -МДж