0
私にはうまく動作するバイナリ検索ツリー用のコードがあります。しかし、私は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：だから、削除機能の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最初に作成されたものです。非常に興味深い、そしてさらに迷惑な。
これはデバッガを使用する完全な**機会である; – Idos
私はデバッガ。それで私のプログラムが削除時に問題になり、最小限のノード機能があることが分かります。 – user3414510
次に、問題を特定のコマンドに絞り込んで何が起こるのを防ぐのでしょうか？ – Idos