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

당신은

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

root 경우에 쓸 수 또는 root->left 경우 nullptr 될 수 있습니다.

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