AVLツリー挿入 - セグメンテーションフォールト

Question

私はHackerrank（https://www.hackerrank.com/challenges/self-balancing-tree）でこの問題をエディタで解決しようとしています。

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)でセグメンテーションフォールトを取得していますが、私は理由を理解することはできません。以下は、私が書いたC++の機能コードです。私はこれに入る前にroot->leftの小切手をnullに入れようとしましたが、それでもseg faultが与えられています。

私はHackerrank inbuiltエディタを使用しているので、主な機能は世話をしています。

それにもかかわらず、デバッグ目的のために、私は（以下メインを追加しました）：

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

nullptrすることができroot場合やroot->left場合は

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

を書き込むことはできません。

AVLツリーにルートのみがあり、正しいノードに挿入する場合は、root->left == nullptrとroot->rightが挿入されたノードです。

したがって、実行はdata < root->left->valに進み、セグメント化エラーが生成されます。このような問題を解決する

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; 
}