AVLTreeの実装について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
流れポインタ

AVLTreeの実装について

#1

投稿記事 by 流れポインタ » 11ヶ月前

AVLTreeにデータを挿入し、木構造をみるプログラムを作成しています。
現在挿入がうまくいっておらず、0~9の値を順に挿入して木を作る際、Insert関数内で必ず53行目のif文に入ってしまい、木構造が作れないでいます。
コンパイル時には、
newavl.c:73:14: 警告: 互換性のないポインタ型からの代入です [デフォルトで有効]
root->left = Insert(root->left, root, data);
^
newavl.c:82:15: 警告: 互換性のないポインタ型からの代入です [デフォルトで有効]
root->right = Insert(root->right, root, data);
^
newavl.c:97:2: エラー: 型 ‘AVL_Node’ を戻すときに互換性のない型です。型 ‘stru
ct AVL_Node **’ が予期されます
return *root;

という警告文がでます。
どこを修正したら正しい動作をするようになるでしょうか?

作成環境はwin8、cygwinです。
よろしくお願いします。

コード: 全て選択

#include <stdio.h>
#include <stdlib.h>

typedef struct AVLNode{	//AVL木の宣言
	struct AVLNode *left;
	struct AVLNode *right;
	int data;	//ノードの値
	int height;	//演算の簡単化のために木の高さも定義
} AVL_Node;

//AVL_Node *root = NULL;

int Height(AVL_Node *root){	//木の高さを求める関数 時間計算量はO(1)
	if(!root)	return -1;
	else		return root->height;
}

AVL_Node *SingleLeftRotate(AVL_Node *x){	//LL回転
	AVL_Node *w = x->left;	//以下3行は回転
	x->left = w->right;
	w->right = x;
	
	if(Height(x->left) >= Height(x->right))	x->height = Height(x->left) + 1;	//以下4行は高さの計算
	else					x->height = Height(x->right) + 1;	
	if(Height(w->left) >= x->height)	w->height = Height(w->left) + 1;
	else					w->height = x->height + 1;
	return w;	//新しいノードを返す
}

AVL_Node *SingleRightRotate(AVL_Node *w){	//RR回転
	AVL_Node *x = w->right;	//以下3行は回転
	w->right = x->left;
	x->left = w;
	
	if(Height(w->left) >= Height(w->right))	w->height = Height(w->left) + 1;	//以下4行は高さの計算
	else					w->height = Height(w->right) + 1;	
	if(Height(x->right) >= w->height)	x->height = Height(x->right) + 1;
	else					x->height = w->height + 1;
	return x;	//新しいノードを返す
}

AVL_Node *DoubleLRRotate(AVL_Node *z){	//LR回転(右回転してから左回転)
	z->left = SingleRightRotate(z->left);	//zの左の子xで右回転
	return SingleLeftRotate(z);
}		//zで左回転

AVL_Node *DoubleRLRotate(AVL_Node *x){	//RL回転(左回転してから右回転)
	x->right = SingleLeftRotate(x->right);
	return SingleRightRotate(x);
}

AVL_Node *Insert(AVL_Node *root, AVL_Node *parent, int data){	//データの挿入
	if(root == NULL){	//根がない場合
		root = (AVL_Node*)malloc(sizeof(AVL_Node));	//メモリ確保
		//printf("Check\n");

		if(root == NULL){	//メモリーが確保できない場合
			printf("Memory Error!\n");
			return NULL;
		}
		else{		//メモリーが確保できたらデータを挿入
			root->data = data;
			root->height = 0;
			root->left = root->right = NULL;
			printf("%d\n",root->data);
		}
	}
	
	else if(data < root->data){	//挿入データが左部分木の場合
		root->left = Insert(root->left, root, data);

		if((Height(root->left) - Height(root->right)) == 2){	//左右部分木の高さの差が2になった(木の平衡が崩れた)場合
			if(data < root->left->data)	root = SingleLeftRotate(root);
			else				root = DoubleLRRotate(root);
		}
	}

	else if(data > root->data){	//挿入データが右部分木の場合
		root->right = Insert(root->right, root, data);
		printf("e");

		if((Height(root->right) - Height(root->left)) == 2){	//左右部分木の高さの差が2になった(木の平衡が崩れた)場合
			if(data < root->right->data)	root = SingleRightRotate(root);
			else				root = DoubleRLRotate(root);
		}
	}
	
	//データがすでに木の中にある場合は、処理を行わない。
	//以下は高さの計算
	if(Height(root->left) >= Height(root->right))	root->height = Height(root->left) + 1;
	else						root->height = Height(root->right) + 1;
	
	printf("%d is inserted\n", root->data);
	return root;
}

AVL_Node *Search(AVL_Node *root, int value){	//探索
	if(root == NULL)		return NULL;
	if(value < root->data)		return Search(root->left, value);
	else if(value > root->data)	return Search(root->right, value);

	return root;	//見つかったデータを返す
}

void print_tree(int depth, AVL_Node *root){	//AVL木の構造を出力
	int i;
	//height = root->height;
	//printf("H=%d\n", depth);

	if(root == NULL){
		return;
	}
	print_tree(depth + 1, root->left);
	//printf("H=%d", depth);
	for(i = 0; i < depth; i++){
		printf(" ");
	}
	printf("%d\n", root->data);
	print_tree(depth + 1, root->right);
	//printf("H=%d", depth);
}

void free_tree(AVL_Node *root){
	if(root == NULL)	return;
	free_tree(root->left);	//子のメモリーを開放
	free_tree(root->right);
	free(root);		//自分を開放
}

int main(void){
	int i, j, num;
	AVL_Node *root = NULL;
	for(i = 0; i < 10; i++){
		j = i;
		Insert(root, root, j);
		printf("%d checked\n", root);
	}
	for(;;){
		print_tree(0, root);	//木の状態を出力
		printf("Choose your operation.  1:add 2:search Other:END ==> ");
		scanf("%d", &num);

		switch(num){
			case 1:
				printf("Input number between 1 and 100. ==>");
				scanf("%d", &i);
				if(i < 1 || i > 100){
					continue;
				}
				Insert(root, root, i);
				break;

			case 2:
				printf("input your searching number.");
				scanf("%d", &i);
				if(Search(root, i) != NULL)	printf("%d is founded.\n", i);
				else				printf("%d is NOT founded.\n", i);
				break;

			default:
				free_tree(root);
				return 0;
		}
	}
}

アバター
みけCAT
記事: 6003
登録日時: 7年前
住所: 千葉県
連絡を取る:

Re: AVLTreeの実装について

#2

投稿記事 by みけCAT » 11ヶ月前

流れポインタ さんが書きました:コンパイル時には、
newavl.c:73:14: 警告: 互換性のないポインタ型からの代入です [デフォルトで有効]
root->left = Insert(root->left, root, data);
^
newavl.c:82:15: 警告: 互換性のないポインタ型からの代入です [デフォルトで有効]
root->right = Insert(root->right, root, data);
^
newavl.c:97:2: エラー: 型 ‘AVL_Node’ を戻すときに互換性のない型です。型 ‘stru
ct AVL_Node **’ が予期されます
return *root;

という警告文がでます。
gcc 7.1.0でコンパイルしたところ、

コード: 全て選択

prog.c: In function 'Insert':
prog.c:52:44: warning: unused parameter 'parent' [-Wunused-parameter]
 AVL_Node *Insert(AVL_Node *root, AVL_Node *parent, int data){ //データの挿入
                                            ^~~~~~
prog.c: In function 'main':
prog.c:136:12: warning: format '%d' expects argument of type 'int', but argument 2 has type 'AVL_Node * {aka struct AVLNode *}' [-Wformat=]
   printf("%d checked\n", root);
           ~^
となっており、printf関数に間違った型のデータを渡すことで未定義動作が発生していることがわかりますが、
提示されたエラーは再現できませんでした。
流れポインタ さんが書きました:どこを修正したら正しい動作をするようになるでしょうか?
きちんと読んでいないので他にも間違いがあるかもしれませんが、
とりあえずInsert関数の第一引数をAVL_Node *型へのポインタにして、呼び出し元の変数を書き換えるようにすると改善しそうです。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

流れポインタ

Re: AVLTreeの実装について

#3

投稿記事 by 流れポインタ » 11ヶ月前

Insert関数の第一引数と言いますと、52行目でAVK_Node *rootとなっているところでしょうか?

アバター
みけCAT
記事: 6003
登録日時: 7年前
住所: 千葉県
連絡を取る:

Re: AVLTreeの実装について

#4

投稿記事 by みけCAT » 11ヶ月前

流れポインタ さんが書きました:Insert関数の第一引数と言いますと、52行目でAVK_Node *rootとなっているところでしょうか?
はい。
それに伴い、Insert関数の実装や呼び出しも書き換える必要があります。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

流れポインタ

Re: AVLTreeの実装について

#5

投稿記事 by 流れポインタ » 11ヶ月前

流れポインタ さんが書きました:Insert関数の第一引数と言いますと、52行目でAVK_Node *rootとなっているところでしょうか?
ありがとうございます。
具体的にどのような形に書き換えるべきかご指南いただけますと幸いです。
お願いいたします。

返信

“C言語何でも質問掲示板” へ戻る