이진 검색 트리의 리프 노드 삭제 - 세그먼트 화 오류

Question

비 재귀 적으로 만든 BST에서 리프 노드를 삭제하려고합니다. 문제는 세그먼트 노드를 삭제할 리프 노드를 삭제하려고 할 때 발생하며 그 이유에 대한 단서가 없습니다. 제가 주석을 작성한 코드가 문제의 원인이라고 생각합니다. 해당 노드를 잘못 삭제하거나 BST에서 노드를 삭제하는 다른 방법이 있습니까?

 #include <stdio.h> 
    #include <stdlib.h> 

     struct BSTnode 
    { 
    int data; 
    struct BSTnode *left,*right,*parent; 

    }; 

    typedef struct BSTnode node; 

    void insert(node **root,int val) 
    { 
    node *ptr,*newptr; 

    newptr=(node *)malloc(sizeof(node)); 
    newptr->left=NULL; 
    newptr->right=NULL; 
    newptr->parent=NULL; 
    newptr->data=val; 

    if((*root)==NULL) 
    { 
    (*root)=newptr; 
    return; 
    } 

    ptr=(*root); 

    while(ptr!=NULL && ptr->data!=val) 
    { 
     if(ptr->data >val) 
    { 
     if(ptr->left!=NULL) 
     ptr=ptr->left; 
     else 
     { 
     ptr->left=newptr; 
     newptr->parent=ptr; 
     break; 
     } 
    } 
    else 
    { 
     if(ptr->right!=NULL) 
     ptr=ptr->right; 
     else 
    { 
     ptr->right=newptr; 
     newptr->parent=ptr; 
     break; 
     } 
    } 
    } 

    } 

    void deleteLeaf(node **root) 
    { 

     node *leafParent=NULL; 

     if((*root)->left!=NULL) 
     deleteLeaf(&((*root)->left)); 

     if((*root)->right!=NULL) 
     deleteLeaf(&((*root)->right)); 


     if((*root)->left==NULL && (*root)->right==NULL) 
    { 

     /* leafParent=(*root)->parent; 

      if(leafParent->left==(*root)) 
      leafParent->left=NULL; 
      else 
      leafParent->right=NULL; 
     */ 

      free(*root); 
     } 
     } 

void inorder(node *root) 
{ 
    if(root->left!=NULL) 
    inorder(root->left); 

    printf(" %d ", root->data); 

    if(root->right!=NULL) 
    inorder(root->right); 
} 

main() 
{ 
node *root=NULL; 
int i,n,val; 

printf("\n How many elements ?"); 
scanf("%d",&n); 

for(i=0;i<n;++i) 
{ 
scanf("%d",&val); 
insert(&root,val); 

} 

printf("\n Inorder traversal : "); 
inorder(root); 

deleteLeaf(&root); 
printf("\n Inorder traversal : "); 
inorder(root); 
} 

Answer 1

는 사실 leafParent-와 그것을 역 참조하면> 왼쪽으로,이 오류를에 세그먼트 바로 다음 거기 (주석) leafParent가 NULL 기능 deleteLeaf의 경우, 그리고. 그래서 다음과 같이 거기에 체크를 넣어해야합니다

leafParent=(*root)->parent; 
    if (leafParent) 
    { 
     if(leafParent->left==(*root)) 
     { 
      leafParent->left=NULL; 
     } 
     else 
     { 
      leafParent->right=NULL; 
     } 
    } 

이쪽 독방 감금 오류를 방지하지만, 기능은 당신이하고 싶은 일을이 끝날 경우 내가 확실하지 오전 것입니다 ... 즉 당신의 논리는 리프 노드를 삭제하기 위해 (아직 시도하고있는 것이 있다면) 약간의 조정이 필요합니다.

Answer 2

나는 실제로 나뭇잎 만 삭제하는 것이 아니라고 생각합니다. 전체 트리를 재귀 적으로 삭제하는 것입니다. 각 노드에 대해 먼저 잎을 삭제 한 다음 잎이 ((left == NULL) && (right == NULL))인지 확인합니다. 이는 분명히 삭제 한 이후입니다. 그것의 자손 - 그리고 그것을 삭제하십시오.

첫 번째 문제는 Chris가 빨리 지적했듯이 leafParent가 NULL이 될 수 있는지 확인하지 못한다는 것입니다. 부모 노드를 루트 노드로 설정하여 NULL을 역 참조하지 않도록하십시오. 다른 문제 (즉, 더 나쁜)는 일단 메모리를 해제하면 포인터를 무효화하지 않는다는 것입니다. 좋은 습관은 포인터를 NULL을 해제하자마자 NULL로 설정하는 것입니다. 나중에 검사를하지 않으면 segfault 할 수 있지만 메모리 덩어리가 다른 구조에 의해 할당 될 때 나중에 포인터를 사용하여 자동으로 메모리가 손상되지 않습니다. 당신을 위해 랩퍼를 작성할 수도 있습니다 (또한 NULL 포인터를 해제하려는 시도를 확인할 수도 있습니다. 실제로는 아무 것도하지 않는 유효한 작업입니다 - 적어도 일부 플랫폼에서는 가능합니다). 이 특별한 경우, 일단 전체 트리 삭제가 끝나면 (실제로 일어나는 것처럼), main() 내부의 제거 된 루트 노드에 대한 포인터를 여전히 가지고 있으며 즉시 사용합니다.

단점이있는 쪽지로, 코드에서 int main(void) { ... } 또는 int main(int argc, int **argv) { ... }이 아닌 main()입니다. :-)