合計 昨日 今日

AVLTreeの実装について

フォーラムルール
フォーラムルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Name: 流れポインタ
[URL]
Date: 2017年5月14日(日) 19:59
No: 1
(OFFLINE)

 AVLTreeの実装について

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です。
よろしくお願いします。

コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#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;
        }
    }
}

Name: みけCAT
[URL]
伝説なるハッカー(675,552 ポイント)
Date: 2017年5月14日(日) 20:40
No: 2
(OFFLINE)

 Re: AVLTreeの実装について

流れポインタ さんが書きました:コンパイル時には、
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でコンパイルしたところ、
コード[Text]: 全て選択
1
2
3
4
5
6
7
8
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で殴ればいい!(死亡フラグ)

Name: 流れポインタ
[URL]
Date: 2017年5月14日(日) 23:23
No: 3
(OFFLINE)

 Re: AVLTreeの実装について

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

Name: みけCAT
[URL]
伝説なるハッカー(675,552 ポイント)
Date: 2017年5月15日(月) 00:52
No: 4
(OFFLINE)

 Re: AVLTreeの実装について

流れポインタ さんが書きました:Insert関数の第一引数と言いますと、52行目でAVK_Node *rootとなっているところでしょうか?

はい。
それに伴い、Insert関数の実装や呼び出しも書き換える必要があります。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

Name: 流れポインタ
[URL]
Date: 2017年5月15日(月) 00:57
No: 5
(OFFLINE)

 Re: AVLTreeの実装について

流れポインタ さんが書きました:Insert関数の第一引数と言いますと、52行目でAVK_Node *rootとなっているところでしょうか?


ありがとうございます。
具体的にどのような形に書き換えるべきかご指南いただけますと幸いです。
お願いいたします。


Return to C言語何でも質問掲示板

オンラインデータ

このフォーラムを閲覧中のユーザー: maru & ゲスト[9人]