はじめての C
splay木を 用いて tree の root を 変更させてみる。 その前に、ポインタを どう渡すか、ちょっと チェック ...
struct Node **tree;
int value;if (*tree == NULL)
new_node(tree, value);
if ((*tree)->left == NULL)
new_node(&(*tree)->left, value);
/* t_splay.c */
#include
#include
#include "t_splay.h"struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Tree {
struct Node *root;
};
int new_node();
int splay_insert();
int splay_search();
void rotate_right();
void rotate_left();
void btree_walk();
int tree_height();
main()
{
int value;
struct Tree *root;
root = NULL;
while (fscanf(stdin, "%d", &value) != EOF)
splay_insert(&root, value);
btree_walk(root);
putchar('\n');
printf("%d\n", tree_height(root));
printf("splay search > %d\n", ROOT);
splay_search(&root, ROOT);
printf("%d\n", tree_height(root));
return 0;
}
int new_node(struct Node **node, int value)
{
*node = malloc(sizeof(**node));
if (*node == NULL)
return 0;
(*node)->data = value;
(*node)->left = NULL;
(*node)->right = NULL;
return 1;
}
int splay_insert(struct Node **tree, int key)
{
int rc;
if (*tree == NULL) {
new_node(tree, key);
rc = (*tree == NULL) ? 0 : 1;
}
else if (key < (*tree)->data) {
if ((*tree)->left == NULL) {
new_node(&(*tree)->left, key);
rc = ((*tree)->left == NULL) ? 0 : 1;
}
else if (key < (*tree)->left->data) {
rc = splay_insert(&(*tree)->left->left, key);
rotate_right(tree);
}
else if (key > (*tree)->left->data) {
rc = splay_insert(&(*tree)->left->right, key);
rotate_left(&(*tree)->left);
}
else
rc = 0;
rotate_right(tree);
}
else if (key > (*tree)->data) {
if ((*tree)->right == NULL) {
new_node(&(*tree)->right, key);
rc = ((*tree)->right == NULL) ? 0 : 1;
}
else if (key < (*tree)->right->data) {
rc = splay_insert(&(*tree)->right->right, key);
rotate_left(tree);
}
else if (key > (*tree)->right->data) {
rc = splay_insert(&(*tree)->right->left, key);
rotate_right(&(*tree)->right);
}
else
rc = 0;
rotate_left(tree);
}
else
rc = 0;
return rc;
}
int splay_search(struct Node **tree, int key)
{
int rc;
if ((*tree)->data == key)
rc = 1;
else if (key < (*tree)->data) {
if ((*tree)->left->data == key)
rc = 1;
else if (key < (*tree)->left->data) {
rc = splay_insert(&(*tree)->left->left, key);
rotate_right(tree);
}
else if (key > (*tree)->left->data) {
rc = splay_insert(&(*tree)->left->right, key);
rotate_left(&(*tree)->left);
}
else
rc = 0;
rotate_right(tree);
}
else if (key > (*tree)->data) {
if ((*tree)->right->data == key)
rc = 1;
else if (key < (*tree)->right->data) {
rc = splay_insert(&(*tree)->right->right, key);
rotate_left(tree);
}
else if (key > (*tree)->right->data) {
rc = splay_insert(&(*tree)->right->left, key);
rotate_right(&(*tree)->right);
}
else
rc = 0;
rotate_left(tree);
}
else
rc = 0;
return rc;
}
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;
}
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;
}
/* t_splay.h */
#define ROOT 30
$cc -c t_splay.c
$cc -o t_splay t_splay.o
$./t_splay < badtree.txt*1:ソート順のデータ
