AVL 树插入 - 分段错误

Question

我正在尝试使用他们的编辑器在 Hackerrank ( https://www.hackerrank.com/challenges/self-balancing-tree ) 上解决这个问题。以下是我写的C++函数代码：

node* makeNewNode (int data)
{
    node* temp= new node();
    temp->val=data;
    temp->left=NULL;
    temp->right=NULL;
    temp->ht=0;
    return temp;
}

//------------------------------------------------------------
int height(node* temp)
{
    if(temp==NULL)
        return -1;
    return temp->ht;
}

//------------------------------------------------------------
int balanceFactor(node* root)
{
    if(root==NULL)
        return 0;
    return height(root->left)-height(root->right);
}

//------------------------------------------------------------
node* rightrotation(node* root)
{
    node* temp1 = root->left;
    node* temp = temp1->right;
    temp1->right = root;
    root->left = temp;
    root->ht = max(height(root->left), height(root->right)) + 1;
    temp1->ht = max(height(temp1->left), height(temp1->right)) + 1;
    return temp1;
}

//------------------------------------------------------------
node* leftrotation(node* root)
{
    node* temp = root->right;
    node* temp1 = temp->left;
    temp->left = root;
    root->right = temp1;
    root->ht = max(height(root->left), height(root->right)) + 1;
    temp->ht = max(height(temp->left), height(temp->right)) + 1;
   return temp;
}

//------------------------------------------------------------
node* insert( node* root, int data)
{
    if(root == NULL)
        return makeNewNode(data);

    if(data<root->val)
        root->left = insert(root->left, data);
    else if(data>root->val)
        root->right = insert(root->right, data);
    else
        return root;

    root->ht = 1 + max(height(root->left), height(root->right));
    int balance = balanceFactor(root);

    if(data<root->left->val && balance>1)
        return rightrotation(root);

    if(data>root->right->val && balance<-1)
        return leftrotation(root);

    if(balance>1 && data > root->left->val)
    {
        root->left = leftrotation(root->left);
        return rightrotation(root);
    }

    if(balance<-1 && data < root->right->val)
    {
        root->right = rightrotation(root->right);
        return leftrotation(root);
    }

    return root;
}

我在行 if(balance>1 && data > root->left->val) 中遇到分段错误，但我不知道为什么。在进入这个之前，我尝试检查 root->left is null，但即使这样也会出现段错误。

因为我使用的是 Hackerrank 内置编辑器，所以主要功能已经完成。

然而，出于调试目的，我添加了以下 main():

int main()
{
node* root=NULL;
root=insert(root,1);
root=insert(root,2);
root=insert(root,3);
return 0;
}

我尝试了在线 gdb (www.onlinegdb.com)，它显示

Program received signal SIGSEGV, Segmentation fault.                                                                                     
0x0000000000400aa2 in insert (root=0x603010, data=2) at main.cpp:86                                                                      
86          if(data<root->left->val && balance>1)

请帮忙。

Answer 1

你不能写

if(data<root->left->val && balance>1)

if root or if root->left 可以是 nullptr.

如果您的 AVL 树只有一个根并且您在正确的节点上插入，则 root->left == nullptr 和 root->right 是您插入的节点。

所以执行会继续data < root->left->val并且会产生段错误。您需要插入更多条件，例如

if(root->left != nullptr && data<root->left->val && balance>1)

这里是修改后的插入函数：

node* insert( node* root, int data)
{
    ...
    int balance = balanceFactor(root);

    if(root->left && data<root->left->val && balance>1) // here was the segmentation fault with gdb
        return rightrotation(root);

    if(root->right && data>root->right->val && balance<-1)
        return leftrotation(root);

    if(balance>1 && root->left && data > root->left->val)
    { ... }

    if(balance<-1 && root->right && data < root->right->val)
    { ... }

    return root;
}

AVL 树插入 - 分段错误

AVL Tree insertion - Segmentation fault

c++

segmentation-fault

avl-tree