AVLツリーが破損してプログラムがクラッシュするのを避けるために

Question

私にはうまく動作するバイナリ検索ツリー用のコードがあります。しかし、私はBSTの削除のためのコードを追加すると、私のプログラムは、その削除中にクラッシュします。

エラーが表示されます。アクセス違反の読み取り場所は0x00000000です。

私はこれがNULLポインタなどを渡すことと関係があると思います。たぶんどこかでそれを読んだり、まったく間違っているし、馬鹿だ。

とにかく、私のAVL削除のコードはこちらです。あなたが私のプログラムを働かせて助けてくれるなら、私が間違ったことを理解するのを助けることができたら、とても感謝しています。私は最小ノードを見つけるための私の機能も含んでいます。なぜなら、あたかもそれが原因であるかのように感じるからです。

AVL min_node(AVL self) 
{ 
    /* A AVL node to keep track of the current node. */ 
    AVL current = self; 


    /* This loop finds the minimum node, by traversing the tree until the leftmost node is discovered. */ 
    while (!empty_tree(current)) 
    { 
     current = current->left; 
    } 

    /* Returns the tree. */ 
    return current; 
} 



AVL delete(AVL self, long id) 
{ 

    if (self != NULL) 
    { 
     if (id == self->student_id) 
     { 
      if (self->left != NULL) 
      { 
       AVL successor = min_node(self->right); 
       self->student_id = successor->student_id; 
       self->right = delete(self->right, self->student_id); 
      } 
      else 
      { 
       AVL to_free = self; 
       if (self->left) 
       { 
        self = self->left; 
       } 
       else 
       { 
        self = self->right; 
       } 
       free(to_free); 
      } 
     } 
     else if (id < self->student_id) 
     { 
      self->left = delete(self->left, id); 
     } 
     else 
     { 
      self->right = delete(self->right, id); 
     } 
    } 

    /*NEW SHIT*/ 
    int balance = getBalance(self); 

    //Left Left Case 
    if (balance > 1 && getBalance(self->left) >= 0) 
    { 
     return rotateRight(self); 
    } 
    //Left Right Case 
    if (balance > 1 && getBalance(self->left) < 0) 
    { 
     self->left = leftRotate(self->left); 
     return rotateRight(self); 
    } 
    //Right Right Case 
    if (balance < -1 && getBalance(self->right) <= 0) 
    { 
     return leftRotate(self); 
    } 
    //Right Left Case 
    if (balance < -1 && getBalance(self->right) > 0) 
    { 
     self->right = rotateRight(self->right); 
     return leftRotate(self); 
    } 

    return self; 
} 

UPDATE：だから、削除機能の2行のいずれかにクラッシュするようだ：

self->student_id = successor->student_id; 

OR

AVL successor = min_node(self->right); 

EDIT 2：要求に応じて、I私のavl.cファイル全体が含まれています。

#include <stdlib.h> 
#include <stdbool.h> 
#include "avl.h" 

bool names_match(char* name_one, char* name_two) 
{ 
    if (strcmp(name_one, name_two) == 0) 
    { 
     return true; 
    } 
    else 
    { 
     return false; 
    } 
} 

bool empty_tree(AVL self) 
{ 
    if (self == NULL) 
    { 
     return true; 
    } 
    else 
    { 
     return false; 
    } 
} 


AVL leftRotate(AVL self) 
{ 
    AVL y = self->right; 
    AVL T2 = y->left; 

    y->left = self; 
    self->right = T2; 

    return y; 
} 

AVL rotateRight(AVL self) 
{ 
    AVL x = self->left; 
    AVL T2 = x->right; 

    x->right = self; 
    self->left = T2; 

    return x; 
} 

int getBalance(AVL node) 
{ 
    if (node == NULL) 
    { 
     return 0; 
    } 
    return height(node->left) - height(node->right); 
} 


AVL insert(AVL self, long id) 
{ 
    if (self == NULL) 
    { 
     self = (AVL)malloc(sizeof(struct avlNode)); 
     self->student_id = id; 
     self->left = self->right = NULL; 
    } 
    else if (id < self->student_id) 
    { 
     self->left = insert(self->left, id); 
    } 
    else if (id > self->student_id) 
    { 
     self->right = insert(self->right, id); 
    } 


    /*NEW SHIT*/ 
    int balance = getBalance(self); 

    //Left Left Case 
    if (balance > 1 && id < self->left->student_id) 
    { 
     return rotateRight(self); 
    } 
    //Right Right Case 
    if (balance < -1 && id > self->right->student_id) 
    { 
     return leftRotate(self); 
    } 
    //Left Right Case 
    if (balance > 1 && id > self->left->student_id) 
    { 
     self->left = leftRotate(self->left); 
     return rotateRight(self); 
    } 
    //Right Left Case 
    if (balance < -1 && id < self->right->student_id) 
    { 
     self->right = rotateRight(self->right); 
     return leftRotate(self); 
    } 

    //Return unchanged pointer (i dunno why. could probably be void) 
    return self; 
} 

/* === AVL MINIMUM NODE === 
Finds the minimum node in a AVL. 
*/ 
AVL min_node(AVL self) 
{ 
    /* A AVL node to keep track of the current node. */ 
    AVL current = self; 

    /* This loop finds the minimum node, by traversing the tree until the leftmost node is discovered. */ 
    while (!empty_tree(current->left)) 
    { 
     current = current->left; 
    } 

    /* Returns the tree. */ 
    return current; 
} 



AVL delete(AVL self, long id) 
{ 
    if (self != NULL) 
    { 
     if (id == self->student_id) 
     { 
      if (self->left != NULL) 
      { 
       AVL successor = min_node(self->right); 
       self->student_id = successor->student_id; 
       self->right = delete(self->right, self->student_id); 
      } 
      else 
      { 
       AVL to_free = self; 
       if (self->left) 
       { 
        self = self->left; 
       } 
       else 
       { 
        self = self->right; 
       } 
       free(to_free); 
      } 
     } 
     else if (id < self->student_id) 
     { 
      self->left = delete(self->left, id); 
     } 
     else 
     { 
      self->right = delete(self->right, id); 
     } 
    } 

    /*NEW SHIT*/ 
    if (self == NULL) 
    { 
     return self; //ADDED TODAY 
    } 

    int balance = getBalance(self); 

    //Left Left Case 
    if (balance > 1 && getBalance(self->left) >= 0) 
    { 
     return rotateRight(self); 
    } 
    //Left Right Case 
    if (balance > 1 && getBalance(self->left) < 0) 
    { 
     self->left = leftRotate(self->left); 
     return rotateRight(self); 
    } 
    //Right Right Case 
    if (balance < -1 && getBalance(self->right) <= 0) 
    { 
     return leftRotate(self); 
    } 
    //Right Left Case 
    if (balance < -1 && getBalance(self->right) > 0) 
    { 
     self->right = rotateRight(self->right); 
     return leftRotate(self); 
    } 

    return self; 
} 

/* === AVL NODE COUNT === 
Counts the number of nodes in the AVL. 
*/ 
int number_of_nodes(AVL self) 
{ 
    /* If the tree is empty, return a count of 0 nodes. */ 
    if (empty_tree(self)) 
    { 
     return(0); 
    } 
    /* If the tree is not empty, but its left and right nodes are, return a count of 1 node. */ 
    else if (empty_tree(self->left) && empty_tree(self->right)) 
    { 
     return(1); 
    } 

    /* If the tree is not empty, and its left and right nodes are also not empty, run this function recursively in the left and right nodes. */ 
    else 
    { 
     return(1 + (number_of_nodes(self->left) + number_of_nodes(self->right))); 
    } 

} 

/* === AVL HEIGHT === 
Returns the total height of a AVL. 
*/ 
int height(AVL self) 
{ 
    /* If the tree is empty, return a count of 0 nodes. */ 
    if (empty_tree(self)) 
    { 
     return 0; 
    } 
    /* If the tree is not empty, run this fucntion recursively on the left and right branches, returning the max of the two. */ 
    else 
    { 
     return 1 + max(height(self->left), height(self->right)); 
    } 
} 



/* === PRINT AVL === 
Prints a AVL in pre-order. 
*/ 
void print_pre_order(AVL self) 
{ 

    /* If the tree isn't empty, print the node's ID and then run this function recursively on the left and then the right nodes, 
    to print pre order. */ 
    if (!empty_tree(self)) 
    { 
     printf("%d", self->student_id); 
     printf("\n"); 
     print_pre_order(self->left); 
     print_pre_order(self->right); 

    } 
} 

/* === SEARCH AVL === 
Searches a AVL for a particular node. 
*/ 
bool searchTree(AVL self, long id) 
{ 
    if (!empty_tree(self)) 
    { 
     /* If the node's ID matches the input ID, return true. */ 
     if (self->student_id == id) 
     { 
      return true; 
     } 

     /* If the node's ID doesn't match the input ID, run this function recurseively on the appropriate node. */ 
     else 
     { 
      if (self->student_id > id) 
      { 
       return searchTree(self->left, id); 
      } 
      else if (self->student_id < id) 
      { 
       return searchTree(self->right, id); 
      } 
     } 
    } 
    return false; 
} 

void destroy_tree(AVL self) 
{ 
    /* If the tree is not empty, free each node in the tree by running this function recursively on the left and right branches. */ 
    if (!empty_tree(self)) 
    { 
     destroy_tree(self->left); 
     destroy_tree(self->right); 
     free(self); 
    } 
} 

EDIT 3：興味深い開発。使用されているAVLツリーは実際にはリンクリストにあり、各ノードにはAVLツリーが含まれています。今、AVLツリー上のノードを削除できることをたくさんのテストを通して知るようになりました。IF最初に作成されたものです。非常に興味深い、そしてさらに迷惑な。

Answer 1

私は、問題はあなたが関数に渡している 'self-> right'であると思います。もし 'self'が私が仮定しているポインタであれば、それは私の意見では '&（self-> right）'のように 'self'の 'address'を渡すべきであり、現在には'& self'のように 'current = * self'のように。それから、私はそれがうまくいくと思う。 コード全体を提供していれば訂正できると思うが、あなたは要点を得ていると思う。