2016-04-24 135 views
0

所以我有一个二进制搜索树在C中的代码工作正常。但是,当我添加BST删除代码时,我的程序将在删除期间崩溃。AVL树删除导致程序崩溃

它给了我一个错误,说访问冲突读取位置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:所以它似乎是对两行删除功能一个崩溃:

self->student_id = successor->student_id; 

OR

AVL successor = min_node(self->right); 

编辑2:根据要求,我包括我的整个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); 
    } 
} 

编辑3:有趣的发展。正在使用的AVL树实际上是在一个链表中,每个节点都包含一个AVL树。现在我已经意识到(通过大量测试)AVL树上的节点可以被删除,它的第一个已经被构建。非常有趣,更令人讨厌。

+2

这是一个**完美**使用调试器的机会;) – Idos

+0

我使用调试器。这就是我知道我的程序在删除时遇到问题以及最小节点功能的原因。 – user3414510

+0

那么是什么阻止你将问题缩小到特定的命令并查看会发生什么? – Idos

回答

0

我认为问题出在您传递给函数的'自适应'上。如果'自我'是一个指针,我认为它是我认为你应该通过'自我'的'地址',就像'&(自>右)',并且当前应该被赋予'& self'like'current = * self'。然后我认为它可以工作。 我想我可以改正我说的话如果我提供的整个代码,但我认为你得到的主意

+0

尝试了你的建议。不幸的是,没有工作。令我感到不快的是,它和我的二进制搜索树一起工作正常。我只是无法弄清楚为什么它与额外的AVL代码崩溃。 – user3414510

+0

你能告诉我整个代码吗? – Vivek

+0

当然,我已将它添加到主帖子中。 – user3414510