Почему моя AVL-вставка возвращает ошибку сегментации после большого входа? - PullRequest
Новая
       32

Почему моя AVL-вставка возвращает ошибку сегментации после большого входа?

0 голосов
/ 21 октября 2019

Я реализую структуру дерева avl. Когда я запускаю операцию вставки, я вижу странную вещь: если ввод достаточно мал, то есть 10 или 20, тогда вставка проходит нормально. Как только я пытаюсь вставить 100 элементов, все идет к ошибке сегмента, и, независимо от того, что я делаю, впоследствии она не работает правильно.

Я пробовал много советов с этого сайта и мою собственную отладку / трассировкубумага, кажется, не может поймать ошибку.

Это моя операция вставки: 

Node *AVLTree::insert(Node *node, int key)
{
    /*
    insert a node into a binary tree.
    */
    if (node == NIL)
    {
        return (newNode(key)); // O(1)
    }
    if (key < node->val)
    {
        node->left = this->insert(node->left, key); // T(n/2)
        node->left->p = node;
    }
    else if (key > node->val)
    {
        node->right = this->insert(node->right, key); // T(n/2)
        node->right->p = node;
    }
    else
    {
        return node;
    }
    node->height = 1 + fmax(height(node->left), height(node->right)); // O(i log i) where i is the number of nodes in the current subtree
    int balance = this->get_balance(node);                            // O(1)
    if (balance > 1 && node->left != NIL && key < node->left->val)
    {
        return this->right_rotate(node); // O(1)
    }
    if (balance > 1 && node->left != NIL && key > node->left->val)
    {
        node->left = this->left_rotate(node->left);
        return this->right_rotate(node); // O(1)
    }
    if (balance < -1 && node->right != NIL && key > node->right->val)
    {
        return this->left_rotate(node); // O(1)
    }
    if (balance < -1 && node->right != NIL && key < node->right->val)
    {
        node->right = this->right_rotate(node->right);
        return this->left_rotate(node); // O(1)
    }
    return node;
}

Это левый и правый повороты 

Node *AVLTree::left_rotate(Node *x)
{
    Node *y = x->right;
    x->right = y->left;
    if (y->left != NIL)
    {
        y->left->p = x;
    }
    y->p = x->p;
    if (x->p == NIL)
    {
        this->root = y;
    }
    else if (x == x->p->left)
    {
        x->p->left = y;
    }
    else
    {
        x->p->right = y;
    }
    y->left = x;
    x->p = y;
    x->height = 1 + fmax(height(x->left), height(x->right));
    y->height = 1 + fmax(height(y->left), height(y->right));
    return y;
}

Node *AVLTree::right_rotate(Node *y)
{
    Node *x = y->left;
    y->left = x->right;
    if (x->right != NIL)
    {
        x->right->p = y;
    }
    x->p = y->p;
    if (y->p == NIL)
    {
        this->root = x;
    }
    else if (y == y->p->left)
    {
        y->p->left = x;
    }
    else
    {
        y->p->right = x;
    }
    x->right = y;
    y->p = x;
    x->height = 1 + fmax(height(x->left), height(x->right));
    y->height = 1 + fmax(height(y->left), height(y->right));
    return x;
}

мой основной кодниже 

int main(int argc, char const *argv[])
{
    vector<int> A = create_random_data(atoi(argv[1]), atoi(argv[2]), atoi(argv[3])); // creates a vector of size argv[1] with random ints between argv[2] and argv[3]
    Node *root = NIL;

    AVLTree tree = AVLTree(root);
    display(A); // displays input array
    for (size_t i = 0; i < A.size(); i++)
    {
        tree.root = tree.insert(tree.root, A[i]);
    }
}

Произошла ошибка в цикле вставки, и я попытался отследить, где именно, но трудно сказать. Спасибо за любую рекомендацию / совет!

...