はじめての C
今度は AVL木。関数 avl_insert では 仮引数が それぞれ 構造体のポインタと 構造体になっているので、メモリの確保が 別に必要となります。
でも、そんなこと できそうにもないので、avl_insert を少し改悪 ? してみることに ...
/* insert_avl.c */
#include
#include
#include "insert_avl.h"int new_node();
int avl_insert();
int compare();
void rotate_left();
void rotate_right();
void btree_walk();
int tree_height();
main()
{
struct Avl *root;
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));
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;
}
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;
}
あと、ヘッダファイルをつくって、構造体の宣言を入れておく。
/* insert_avl.h */struct Avl {
struct Avl *left;
struct Avl *right;
int balance;
int data;
};
コンパイルして、random.txt と badtree.txt とで確認。
$cc -c insert_avl.c
$cc -o insert_avl insert_avl.o
$./insert_avl < random.txt
$./insert_avl < badtree.txtこれ、最強 ... ですね。
