Вставка в дерево AVL: ошибка ошибки сегментации

Question

Я сделал дерево avl, и оно успешно компилируется.однако, пока он вставляет, он вставляет только 1 число и делает ошибку сегментации.Где мне нужно изменить, чтобы сделать код успешным?

Я получил справку из этого файла https://www.geeksforgeeks.org/avl-tree-set-1-insertion/ и сделал статическую внутреннюю функцию _insert, чтобы код выглядел проще.

/* internal function
This function uses recursion to insert the new data into a leaf node
return  pointer to new root
*/
static NODE *_insert(NODE *root, NODE *newPtr)
{
    if (root) return newPtr;

    if (newPtr->data < root->data)
        root->left = _insert(root->left, newPtr);
    else if (newPtr->data >= root->data)
        root->right = _insert(root->right, newPtr);

    root->height = 1 + max(root->left->height, root->right->height);

    int bal = getHeight(root);

    if (bal > 1 && newPtr->data < root->left->data)
        return rotateRight(root);
    if (bal<-1 && newPtr->data > root->right->data)
        return rotateLeft(root);
    if (bal > 1 && newPtr->data > root->left->data)
    {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }
    if (bal < -1 && newPtr->data < root->right->data)
    {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }

    return root;
}

int AVL_Insert(AVL_TREE *pTree, int data)
{
    NODE *pNode = _makeNode(data);
    if (!pNode) return 0;

    pTree->root = _insert(pTree->root, pNode);
    if (!pTree->root) return 0;
    else return 1;
}
``````
````````````
/* internal function
Exchanges pointers to rotate the tree to the right
updates heights of the nodes
return  new root
*/
static NODE *rotateRight(NODE *root)
{
    NODE *t1 = root->left;
    NODE *t2 = t1->right;

    t1->right = root;
    root->left = t2;

    root->height = max(root->left->height, root->right->height) + 1;
    t1->height = max(t1->left->height, t1->right->height) + 1;

    return t1;
}

/* internal function
Exchanges pointers to rotate the tree to the left
updates heights of the nodes
return  new root
*/
static NODE *rotateLeft(NODE *root) 
{
    NODE *t1 = root->right;
    NODE *t2 = t1->left;

    t1->left = root;
    root->right = t2;

    root->height = max(root->left->height, root->right->height) + 1;
    t1->height = max(t1->left->height, t1->right->height) + 1;

}

//main code
srand(time(NULL));
    for (int i = 0; i < MAX_ELEM; i++)
    {
        data = rand() % (MAX_ELEM * 3) + 1; // random number
                                            // data = i+1; // sequential number

        fprintf(stdout, "%d ", data);

        // insert function call
        AVL_Insert(tree, data);
    }
    fprintf(stdout, "\n");

Когда я запускаю Visual Studio, я вставляю только 1 номер. И когда я запускаю это в Linux, я получаю ошибку сегментации (ядро сброшено)

Как я могу решить эту проблему?спасибо

Answer 1

Вы ошиблись здесь:

static NODE *_insert(NODE *root, NODE *newPtr)
{
    if (root) return newPtr;

Когда есть нет корня (то есть пустое дерево), тогда новое дерево состоит исключительно из нового узла. Следовательно, это должно быть:

    if (!root) return newPtr;

Это означает, что ваша ошибка сегментации происходит в следующей строке:

if (newPtr->data < root->data)

потому что вы разыменовываете нулевой указатель root здесь.