はじめての C

ランダム関数 rand() を 利用した balance tree を つくってみる。 RAND_MAX は 生成される 乱数の範囲 (K&R 2nd p317)。 ライブラリ time.h を 使って srand() の引数を 決めるようにした。

/* rand_insert.c */

#include 

#include 

#include 
struct Node {

    int data;

    struct Node *left;

    struct Node *right;

};
struct Tree {

    struct Node *root;

};
int insert();

int norm_insert();

int root_insert();
void btree_walk();

int tree_height();
void rotate_right();

void rotate_left();
main()

{

    int value;

    struct Tree *root;
    srand(time(NULL));
    root = NULL;

    while (fscanf(stdin, "%d", &value) != EOF)

        insert(&root, value);

    btree_walk(root);

    putchar('\n');

    printf("%d\n", tree_height(root));
    return 0;

}
int insert(struct Node **tree, int key)

{

    if (rand() < RAND_MAX/2)

        return root_insert(tree, key);

    else

        return norm_insert(tree, key);

}
int norm_insert(struct Node **tree, int key)

{

    int rc;
    if (*tree == NULL) {

        *tree = malloc(sizeof(**tree));

        if (*tree == NULL)

            rc = 0;

        (*tree)->data = key;

        (*tree)->left = NULL;

        (*tree)->right = NULL;

        rc = 1;

    }

    else if (key < (*tree)->data)

        rc = norm_insert(&(*tree)->left, key);

    else if (key > (*tree)->data)

        rc = norm_insert(&(*tree)->right, key);

    else

        rc = 0;

    return rc;

}
int root_insert(struct Node **tree, int key)

{

    int rc;
    if (*tree == NULL) {

        *tree = malloc(sizeof(**tree));

        if (*tree == NULL)

            rc = 0;

        (*tree)->data = key;

        (*tree)->left = NULL;

        (*tree)->right = NULL;

        rc = 1;

    }

    else if (key < (*tree)->data) {

        rc = root_insert(&(*tree)->left, key);

        rotate_right(tree);

    }

    else if (key > (*tree)->data) {

        rc = root_insert(&(*tree)->right, key);

        rotate_left(tree);

    }

    else

        rc = 0;

    return rc;

}
void btree_walk(struct Node *tree)

{

    if (tree == NULL)

        return;

    btree_walk(tree->left);

    printf("%d ", tree->data);

    btree_walk(tree->right);

}
int tree_height(struct Node *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;

}
void rotate_right(struct Node **root)

{

    struct Node *save;
    save = (*root)->left;

    (*root)->left = save->right;

    save->right = *root;

    *root = save;

}
void rotate_left(struct Node **root)

{

    struct Node *save;
    save = (*root)->right;

    (*root)->right = save->left;

    save->left = *root;

    *root = save;

}

入力データとして ソート順のテキストを準備 ... あれっ? どうやって つくるんだった? (;_;)

/* badtree.c */

#include 

#define MAX 100
main()

{

    int i, n;
    n = 0;

    for (i = 0; i < MAX; i++) {

        n = i;

        printf("%d ", n);

    }

    putchar('\n');
    return 0;

}

ソートデータを 作成。

$cc -o badtree badtree.c

$./badtree > badtree.txt

コンパイルして、確認。 t_balance と 比べてみる。

$cc -c rand_insert.c

$cc -o rand_insert rand_insert.o

$./rand_insert < random.txt

$./t_balance < badtree.txt

$./rand_insert < badtree.txt