所以我有一个二进制搜索树在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树上的节点可以被删除,它的第一个已经被构建。非常有趣,更令人讨厌。
这是一个**完美**使用调试器的机会;) – Idos
我使用调试器。这就是我知道我的程序在删除时遇到问题以及最小节点功能的原因。 – user3414510
那么是什么阻止你将问题缩小到特定的命令并查看会发生什么? – Idos