Возникли проблемы с методом вставки дерева AVL - PullRequest
Новая
       13

Возникли проблемы с методом вставки дерева AVL

0 голосов
/ 04 апреля 2020

Я пытаюсь реализовать дерево AVL в c ++, и я сделал два метода вставки: один publi c, который будет вызываться пользователем, и один private, который будет вызываться рекурсивно, чтобы я мог поддерживать баланс дерева. Тем не менее, он не работает, и он только вставляет root, в то время как любая другая вставка будет потеряна, и я не знаю почему. Я подозреваю, что это дело с указателями, но я не могу понять это. Вот код:

(мне также показались странные попытки увидеть, какие блоки команд выполнялись, а какие нет) 

void AVLTree::Insert(string &key)
{
    if(root)
    {
        bool found = false;
        Insert(key, root, nullptr, found);
    }
    else
    {
        root = new Node(key);

        cout<<root->word<<"|"<<root->balance<<endl;

        if(!root)
            cout<<"Memory allocation failed";
    }
}

void AVLTree::Insert(string &key, Node* currentNode, Node* previousNode, bool &found)
{
    if(!currentNode)
    {
        currentNode = new Node(key);

        if(!currentNode)
            cout<<"Memory allocation failed"<<endl;

        cout<<currentNode->word<<"||"<<currentNode->balance<<endl;
        return;
    }

    if(key > currentNode->word)
        Insert(key, currentNode->right, currentNode, found);
    else if(key < currentNode->word)
        Insert(key, currentNode->left, currentNode, found);
    else
        {
            currentNode->occurences++;
            found = true;
            return;
        }

    if(!found) //we adjust the balance of the tree only if there was a new insertion and not just an increase in an already existing node's occurences
    {
        if(previousNode)
        {
            if(currentNode == previousNode->right)
                previousNode->balance++;
            else                            //we assume that an insertion in the right subtree increases the balance by one while an insertion in the left subtree decreases it by one
                previousNode->balance--;
        }
    }

    cout<<currentNode->word<<"|||"<<currentNode->balance<<endl;
}
...