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的支票是null，但即使这样也是给了seg故障。

因为我使用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) 

如果root或者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; 
}