0
So habe ich Code für eine binäre Suchbaum in C, die gut für mich funktioniert. Wenn ich jedoch Code für eine BST-Löschung hinzufüge, stürzt mein Programm während dieser Löschung ab.AVL Tree Deletion verursacht Programm zum Absturz
Es gibt mir eine Fehlermeldung Zugriff auf die Verletzung Leseort 0x00000000.
Ich denke, das ist etwas mit der Weitergabe von NULL-Zeigern oder etwas zu tun. Vielleicht lese ich das irgendwo, oder vielleicht ist das völlig falsch und ich bin albern.
Wie auch immer, hier ist mein Code für meine AVL-Löschung. Wenn Sie mir helfen könnten, mein Programm in Gang zu bringen und mir helfen zu verstehen, was ich falsch gemacht habe, wäre ich sehr dankbar. Ich werde auch meine Funktion für die Suche nach dem minimalen Knoten einschließen, weil ich das Gefühl habe, dass es der Schuldige sein könnte.
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: So ist es auf einer der beiden Linien in Löschfunktion zu Absturz scheint:
self->student_id = successor->student_id;
ODER
AVL successor = min_node(self->right);
EDIT 2: Auf Wunsch I habe meine gesamte avl.c-Datei enthalten.
#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: Interessante Entwicklung. Der verwendete AVL-Baum befindet sich tatsächlich in einer verknüpften Liste, wobei jeder Knoten einen AVL-Baum enthält. Jetzt habe ich festgestellt (durch viele Tests), dass ein Knoten in der AVL-Struktur gelöscht werden kann, IF ist die erste, die gebaut wurde. Sehr interessant und noch nerviger.
Dies ist eine ** perfekte ** Möglichkeit, einen Debugger zu verwenden;) – Idos
Ich benutze die Debugger. Das ist, wie ich weiß, dass mein Programm zu einem Problem beim Löschen und der minimalen Knotenfunktion kommt. – user3414510
Was verhindert dann, dass Sie Ihr Problem auf einen bestimmten Befehl eingrenzen und sehen, was passiert? – Idos