Здравствуйте. Есть код на СИ, реализующий бинарное дерево. И вот в этом коде упорно косячит метод удаления узла из дерева. Причем я не могу понять, где конкретно, потому что это может случиться и после 500 удалений, и после 1000. Помогите, пожалуйста, найти ошибку. Код ниже.
typedef struct binaryTreeItem
{
//char *key;
keyType key;
int value;
struct binaryTreeItem *left;
struct binaryTreeItem *right;
struct binaryTreeItem *parent;
} BinaryTreeItem;
#define BINARYTREE_ITEM_SIZE sizeof(BinaryTreeItem)
static BinaryTreeItem *BinaryTree;
void AddBinaryTreeItem(keyType key, int value)
{
BinaryTreeItem *current, *newBinaryTreeItem;
newBinaryTreeItem = (BinaryTreeItem*) mm_alloc(BINARYTREE_ITEM_SIZE);
newBinaryTreeItem->key = key;
newBinaryTreeItem->value = value;
if(BinaryTree!=NULL)
{
current=BinaryTree;
while(1)
{
if(key < current->key)
{
if(current->left!=NULL)
current=current->left;
else
{
newBinaryTreeItem->parent = current;
current->left = newBinaryTreeItem;
break;
}
}
else if(key > current->key)
{
if(current->right!=NULL)
current=current->right;
else
{
newBinaryTreeItem->parent = current;
current->right = newBinaryTreeItem;
break;
}
}
else
break;
}
}
else
BinaryTree = newBinaryTreeItem;
}
BinaryTreeItem *find_node(keyType key)
{
BinaryTreeItem *current=BinaryTree;
while(current!=NULL)
{
if(key<current->key)
current=current->left;
else if(key>current->key)
current=current->right;
else
return current;
}
return NULL;
}
int* GetBinaryTreeValueByKey(keyType key)
{
BinaryTreeItem *p;
p = find_node(key);
if(p==NULL)return NULL;
return &p->value;
}
BinaryTreeItem *get_successor(BinaryTreeItem *node)
{
BinaryTreeItem *current;
if(node==NULL)
return NULL;
if(node->right!=NULL)
{
for(current=node->right;;current=current->left)
if(current->left==NULL)
return current;
}
else
{
for(current=node;current->parent!=NULL;current=current->parent)
if(current==current->parent->left)
return current->parent;
return NULL;
}
}
void Remove(BinaryTreeItem *node)
{
BinaryTreeItem *succesor;
if(node==NULL)
return;
if(node->left!=NULL&&node->right!=NULL)
{
succesor=get_successor(node);
node->key=succesor->key;
node->value=succesor->value;
Remove(succesor);
}
else if(node->left!=NULL)
{
node->left->parent=node->parent;
if(node==node->parent->left)
node->parent->left=node->left;
else
node->parent->right=node->left;
mm_free((char*)node);
}
else if(node->right!=NULL)
{
node->right->parent=node->parent;
if(node==node->parent->right)
node->parent->right=node->right;
else
node->parent->left=node->right;
mm_free((char*)node);
}
else
{
if(node->parent->left==node)
node->parent->left=NULL;
else
node->parent->right=NULL;
mm_free((char*)node);
}
}
void DeleteBinaryTreeItem(keyType key)
{
BinaryTreeItem *node;
node = find_node(key);
Remove(node);
}