はじめての C
AVL木の削除。 関数 avl_remove では 再帰が 使われてるが、引数に successor を とってる 箇所が ある。 あまり 安易には いじれないみたいだ。
なので、削除するデータを含む ノードを 返り値とする 検索関数を はさんでみた。
元にした search 関数は コチラ。
http://bal4u.dip.jp/algo/avlTree.txt
/* delete_avl.c */
#include
#include
#include "avl.h"int new_node();
int avl_insert();
struct Avl *avl_search();
int avl_remove();
int compare();
void rotate_left();
void rotate_right();
void btree_walk();
int tree_height();
main()
{
struct Avl *root, *remove;
int value;
root = NULL;
while (fscanf(stdin, "%d", &value) != EOF)
avl_insert(&root, value);
btree_walk(root);
putchar('\n');
printf("%d\n", tree_height(root));
printf("removing item now > %d\n\n", DELETE);
remove = avl_search(root, DELETE);
avl_remove(&root, remove);
free(remove);
btree_walk(root);
putchar('\n');
printf("%d\n", tree_height(root));
return 0;
}
int new_node(struct Avl **node, int value)
{
*node = malloc(sizeof(**node));
if (*node == NULL)
return 0;
(*node)->data = value;
(*node)->balance = 0;
(*node)->left = NULL;
(*node)->right = NULL;
return 1;
}
int avl_insert(struct Avl **tree, int new_item)
{
/* empty tree */
if (*tree == NULL) {
return new_node(tree, new_item);
}
if (compare((*tree)->data, new_item) > 0) {
/* Move left */
if ((*tree)->left != NULL) {
if (avl_insert(&(*tree)->left, new_item) != 0) {
/* balancing act */
if ((*tree)->balance++ < 1)
return (*tree)->balance;
else if ((*tree)->left->balance > 0) {
/* Case 1 */
rotate_right(tree);
(*tree)->balance = 0;
(*tree)->right->balance = 0;
}
else {
/* Case 2 */
rotate_left(&(*tree)->left);
rotate_right(tree);
/* Adjust balance factors */
if ((*tree)->balance == 1) {
(*tree)->left->balance = -1;
(*tree)->right->balance = 0;
}
else if ((*tree)->balance == 0) {
(*tree)->left->balance = 0;
(*tree)->right->balance = 0;
}
else {
(*tree)->left->balance = 0;
(*tree)->right->balance = 1;
}
(*tree)->balance = 0;
}
}
else
return 0;
}
else {
new_node(&(*tree)->left, new_item);
return ++(*tree)->balance;
}
}
else if (compare((*tree)->data, new_item) < 0) {
/* Move right */
if ((*tree)->right != NULL) {
if (avl_insert(&(*tree)->right, new_item) != 0) {
/* balancing act */
if ((*tree)->balance++ < 1)
return (*tree)->balance;
else if ((*tree)->right->balance > 0) {
/* Case 1 */
rotate_left(tree);
(*tree)->balance = 0;
(*tree)->left->balance = 0;
}
else {
/* Case 2 */
rotate_right(&(*tree)->right);
rotate_left(tree);
/* Adjust balance factors */
if ((*tree)->balance == 1) {
(*tree)->left->balance = -1;
(*tree)->right->balance = 0;
}
else if ((*tree)->balance == 0) {
(*tree)->left->balance = 0;
(*tree)->right->balance = 0;
}
else {
(*tree)->left->balance = 0;
(*tree)->right->balance = 1;
}
(*tree)->balance = 0;
}
}
else
return 0;
}
else {
new_node(&(*tree)->right, new_item);
return ++(*tree)->balance;
}
}
return 0;
}
struct Avl *avl_search(struct Avl *tree, int key)
{
struct Avl *node;
node = tree;
while (node != NULL) {
if (key == node->data)
return node;
if (key < node->data)
node = node->left;
else
node = node->right;
}
return NULL;
}
int avl_remove(struct Avl **tree, struct Avl *old_item)
{
struct Avl *heir;
int rv;
/* Delete */
if (*tree == old_item) {
if ((*tree)->left == NULL && (*tree)->right == NULL) {
/* No children, unlink the node */
*tree = 0;
return 1;
}
else if ((*tree)->left == NULL) {
/* Replace node with right child */
*tree = (*tree)->right;
return 1;
}
else if ((*tree)->right == NULL) {
/* Replace node with left child */
*tree = (*tree)->left;
return 1;
}
if ((*tree)->balance < 0) {
/* Find left successor */
heir = (*tree)->left;
while (heir->right != NULL)
heir = heir->right;
}
else {
/* Find right successor */
heir = (*tree)->right;
while (heir->left != NULL)
heir = heir->left;
}
/* Rebalance */
rv = avl_remove(tree, heir);
/* Remove node */
heir->left = (*tree)->left;
heir->right = (*tree)->right;
heir->balance = (*tree)->balance;
*tree = heir;
if (heir->balance == 0)
return rv;
}
/* Search */
if (compare((*tree)->data, old_item->data) > 0) {
/* Move left */
if ((*tree)->left != NULL) {
if (avl_remove(&(*tree)->left, old_item) != 0) {
/* Balancing act */
if ((*tree)->balance++ < 1)
return (*tree)->balance;
else if ((*tree)->right->balance == 0) {
rotate_left(tree);
(*tree)->balance = -1;
(*tree)->left->balance = 1;
return 0;
}
else if ((*tree)->left->balance == 1) {
rotate_left(tree);
(*tree)->balance = 0;
(*tree)->left->balance = 0;
}
else {
rotate_right(&(*tree)->right);
rotate_left(tree);
/* Adjust balance factors */
if ((*tree)->balance == 1) {
(*tree)->left->balance = -1;
(*tree)->right->balance = 0;
}
else if ((*tree)->balance == 0) {
(*tree)->left->balance = 0;
(*tree)->right->balance = 0;
}
else {
(*tree)->left->balance = 0;
(*tree)->right->balance = 1;
}
(*tree)->balance = 0;
}
return 1;
}
}
}
else if (compare((*tree)->data, old_item->data) < 0) {
/* Move right */
if ((*tree)->right != NULL) {
if (avl_remove(&(*tree)->right, old_item) != 0) {
/* Balancing act */
if ((*tree)->balance-- > -1)
return (*tree)->balance;
else if ((*tree)->left->balance == 0) {
rotate_right(tree);
(*tree)->balance = 1;
(*tree)->right->balance = -1;
return 0;
}
else if ((*tree)->left->balance == -1) {
rotate_right(tree);
(*tree)->balance = 0;
(*tree)->right->balance = 0;
}
else {
rotate_left(&(*tree)->left);
rotate_right(tree);
/* Adjust balance factors */
if ((*tree)->balance == 1) {
(*tree)->left->balance = -1;
(*tree)->right->balance = 0;
}
else if ((*tree)->balance == 0) {
(*tree)->left->balance = 0;
(*tree)->right->balance = 0;
}
else {
(*tree)->left->balance = 0;
(*tree)->right->balance = 1;
}
(*tree)->balance = 0;
}
return 1;
}
}
}
return 0;
}
int compare(int a, int b)
{
if (a < b)
return -1;
else if (a > b)
return +1;
else
return 0;
}
void rotate_left(struct Avl **subtree)
{
struct Avl *save;
struct Avl *node;
node = *subtree;
save = node->right;
node->right = save->left;
save->left = node;
*subtree = save;
}
void rotate_right(struct Avl **subtree)
{
struct Avl *save;
struct Avl *node;
node = *subtree;
save = node->left;
node->left = save->right;
save->right = node;
*subtree = save;
}
void btree_walk(struct Avl *tree)
{
if (tree == NULL)
return;
btree_walk(tree->left);
printf("%d ", tree->data);
btree_walk(tree->right);
}
int tree_height(struct Avl *tree)
{
int left_height;
int right_height;
if (tree == NULL)
return -1;
left_height = tree_height(tree->left);
right_height = tree_height(tree->right);
if (left_height < right_height)
return right_height + 1;
else
return left_height + 1;
}
/* avl.h */struct Avl {
struct Avl *left;
struct Avl *right;
int balance;
int data;
};
#define DELETE /* ← 削除するデータを記入 */
$cc -c delete_avl.c
$cc -o delete_avl delete_avl.o
$./delete_avl < random.txt(追記) debian で うまく いかなかった件、単なる コードの 写しまちがいでした。 上のプログラムで ダイジョウブだった ... (;_;) (05/10/8)
(関数 compare の 位置を、プロトタイプ宣言どおりに 変更 - 他は いじってません)
