回答編集履歴
9
count_black関数のcount引数が不要だったので削除
test
CHANGED
@@ -40,16 +40,16 @@
|
|
40
40
|
return true;
|
41
41
|
}
|
42
42
|
|
43
|
-
int count_black(struct rb_node *t
|
43
|
+
int count_black(struct rb_node *t){//条件3、左右不一致なら-1
|
44
|
-
if (t == NULL) return
|
44
|
+
if (t == NULL) return 0;
|
45
|
-
int left_black = count_black(t->left
|
45
|
+
int left_black = count_black(t->left);
|
46
|
-
if (left_black == -1 || left_black != count_black(t->right
|
46
|
+
if (left_black == -1 || left_black != count_black(t->right)) return -1;
|
47
|
-
return
|
47
|
+
return t->black + left_black;
|
48
48
|
}
|
49
49
|
|
50
50
|
bool is_rbtree(struct rb_node *t) {//赤黒木なら1を返す
|
51
51
|
//条件2,3に適するならばtrue、さもなくばfalse
|
52
|
-
return is_order_ok(t) && count_black(t
|
52
|
+
return is_order_ok(t) && count_black(t) != -1;
|
53
53
|
}
|
54
54
|
|
55
55
|
int main() {
|
8
真偽値を返す関数の戻り値の型を bool に変更
test
CHANGED
@@ -26,11 +26,11 @@
|
|
26
26
|
}
|
27
27
|
}
|
28
28
|
|
29
|
-
|
29
|
+
bool is_red(struct rb_node *t){
|
30
30
|
return t != NULL && !t->black;
|
31
31
|
}
|
32
32
|
|
33
|
-
|
33
|
+
bool is_order_ok(struct rb_node *t){//条件2
|
34
34
|
//赤い節点の子が赤ならば条件に反するのでfalseを返す
|
35
35
|
if(is_red(t) && (is_red(t->left) || is_red(t->right))) return false;
|
36
36
|
//左右の葉に到達するまで同様に調べる
|
@@ -47,7 +47,7 @@
|
|
47
47
|
return count + t->black + left_black;
|
48
48
|
}
|
49
49
|
|
50
|
-
|
50
|
+
bool is_rbtree(struct rb_node *t) {//赤黒木なら1を返す
|
51
51
|
//条件2,3に適するならばtrue、さもなくばfalse
|
52
52
|
return is_order_ok(t) && count_black(t, 0) != -1;
|
53
53
|
}
|
7
stdbool.h を使って、真偽値を true, false に変更
test
CHANGED
@@ -3,6 +3,7 @@
|
|
3
3
|
```c
|
4
4
|
#include<stdio.h>
|
5
5
|
#include<stdlib.h>
|
6
|
+
#include<stdbool.h>
|
6
7
|
|
7
8
|
char buf[128];
|
8
9
|
struct map { int id; char name[32];};
|
@@ -30,13 +31,13 @@
|
|
30
31
|
}
|
31
32
|
|
32
33
|
int is_order_ok(struct rb_node *t){//条件2
|
33
|
-
//赤い節点の子が赤ならば条件に反するので
|
34
|
+
//赤い節点の子が赤ならば条件に反するのでfalseを返す
|
34
|
-
if(is_red(t) && (is_red(t->left) || is_red(t->right))) return
|
35
|
+
if(is_red(t) && (is_red(t->left) || is_red(t->right))) return false;
|
35
|
-
//左右の葉に到達するまで
|
36
|
+
//左右の葉に到達するまで同様に調べる
|
36
|
-
if (t->left && is_order_ok(t->left)
|
37
|
+
if (t->left && !is_order_ok(t->left)) return false;
|
37
|
-
if (t->right && is_order_ok(t->right)
|
38
|
+
if (t->right && !is_order_ok(t->right)) return false;
|
38
|
-
//条件に適するので
|
39
|
+
//条件に適するのでtrueを返す
|
39
|
-
return
|
40
|
+
return true;
|
40
41
|
}
|
41
42
|
|
42
43
|
int count_black(struct rb_node *t, int count){//条件3、左右不一致なら-1
|
@@ -47,7 +48,7 @@
|
|
47
48
|
}
|
48
49
|
|
49
50
|
int is_rbtree(struct rb_node *t) {//赤黒木なら1を返す
|
50
|
-
//条件2,3に適するならば
|
51
|
+
//条件2,3に適するならばtrue、さもなくばfalse
|
51
52
|
return is_order_ok(t) && count_black(t, 0) != -1;
|
52
53
|
}
|
53
54
|
|
6
変数名・関数名見直し
test
CHANGED
@@ -12,44 +12,43 @@
|
|
12
12
|
struct rb_node* get_rbtree() {
|
13
13
|
struct rb_node *t;
|
14
14
|
char c;
|
15
|
-
if(fgets(buf,sizeof(buf),stdin)==NULL || buf[0]=='.'){
|
15
|
+
if(fgets(buf,sizeof(buf),stdin) == NULL || buf[0] == '.'){
|
16
16
|
/* ドットだけなら葉 (NULL) を返す */
|
17
17
|
return NULL;
|
18
18
|
} else {
|
19
19
|
/* ドットでなければ節点を表す構造体のアドレス t を用意 */
|
20
20
|
t = (struct rb_node*)malloc(sizeof(struct rb_node));
|
21
21
|
sscanf(buf,"[%c]%d,%[^,]",&c,&t->data.id,t->data.name);
|
22
|
-
t->black = c=='b';
|
22
|
+
t->black = c == 'b';
|
23
23
|
t->left = get_rbtree(); t->right = get_rbtree();
|
24
24
|
return t;
|
25
25
|
}
|
26
26
|
}
|
27
27
|
|
28
28
|
int is_red(struct rb_node *t){
|
29
|
-
return t!=NULL && !t->black;
|
29
|
+
return t != NULL && !t->black;
|
30
30
|
}
|
31
31
|
|
32
|
-
int
|
32
|
+
int is_order_ok(struct rb_node *t){//条件2
|
33
33
|
//赤い節点の子が赤ならば条件に反するので0を返す
|
34
34
|
if(is_red(t) && (is_red(t->left) || is_red(t->right))) return 0;
|
35
|
-
//左右
|
35
|
+
//左右の葉に到達するまで再帰的に調べる
|
36
|
-
if (t->left &&
|
36
|
+
if (t->left && is_order_ok(t->left) == 0) return 0;
|
37
|
-
if (t->right &&
|
37
|
+
if (t->right && is_order_ok(t->right) == 0) return 0;
|
38
38
|
//条件に適するので1を返す
|
39
39
|
return 1;
|
40
40
|
}
|
41
41
|
|
42
|
-
int
|
42
|
+
int count_black(struct rb_node *t, int count){//条件3、左右不一致なら-1
|
43
|
-
if (t==NULL) return count;
|
43
|
+
if (t == NULL) return count;
|
44
|
-
int
|
44
|
+
int left_black = count_black(t->left, 0);
|
45
|
-
if (
|
45
|
+
if (left_black == -1 || left_black != count_black(t->right, 0)) return -1;
|
46
|
-
return count + t->black +
|
46
|
+
return count + t->black + left_black;
|
47
47
|
}
|
48
48
|
|
49
49
|
int is_rbtree(struct rb_node *t) {//赤黒木なら1を返す
|
50
|
-
int is_order_ok = check_color(t)==1;
|
51
|
-
|
50
|
+
//条件2,3に適するならば1、さもなくば0
|
52
|
-
return is_order_ok &&
|
51
|
+
return is_order_ok(t) && count_black(t, 0) != -1;
|
53
52
|
}
|
54
53
|
|
55
54
|
int main() {
|
5
変数名見直し
test
CHANGED
@@ -47,9 +47,9 @@
|
|
47
47
|
}
|
48
48
|
|
49
49
|
int is_rbtree(struct rb_node *t) {//赤黒木なら1を返す
|
50
|
-
int
|
50
|
+
int is_order_ok = check_color(t)==1;
|
51
|
-
int con
|
51
|
+
int is_count_ok = setten(t, 0)!=-1;
|
52
|
-
return
|
52
|
+
return is_order_ok && is_count_ok; //条件2,3に適するならば1、さもなくば0
|
53
53
|
}
|
54
54
|
|
55
55
|
int main() {
|
4
比較演算子の空白を削除して統一
test
CHANGED
@@ -26,7 +26,7 @@
|
|
26
26
|
}
|
27
27
|
|
28
28
|
int is_red(struct rb_node *t){
|
29
|
-
return t
|
29
|
+
return t!=NULL && !t->black;
|
30
30
|
}
|
31
31
|
|
32
32
|
int check_color(struct rb_node *t){//条件
|
3
追記の位置がおかしかったので修正
test
CHANGED
@@ -1,21 +1,4 @@
|
|
1
|
-
とりあえず、気付いた点だけ。
|
2
|
-
|
3
|
-
> ```C
|
4
|
-
> check_color(t->left);
|
5
|
-
> check_color(t->right);
|
6
|
-
> return 1;//条件に適するので1を返す
|
7
|
-
> ```
|
8
|
-
|
9
|
-
check_colorの戻り値によって、0か1を返すのではありませんか?
|
10
|
-
|
11
|
-
ソースコードに手を入れてみました。
|
1
|
+
追記: ソースコードに手を入れてみました。
|
12
|
-
|
13
|
-
> ```c
|
14
|
-
> int savecount;
|
15
|
-
> ```
|
16
|
-
|
17
|
-
グローバル変数を使っていることに不安を覚えました。
|
18
|
-
-1 か判定してますけど、どんなときに -1 になりますか?
|
19
2
|
|
20
3
|
```c
|
21
4
|
#include<stdio.h>
|
@@ -76,3 +59,23 @@
|
|
76
59
|
}
|
77
60
|
```
|
78
61
|
|
62
|
+
最初のコメント:
|
63
|
+
|
64
|
+
とりあえず、気付いた点だけ。
|
65
|
+
|
66
|
+
> ```C
|
67
|
+
> check_color(t->left);
|
68
|
+
> check_color(t->right);
|
69
|
+
> return 1;//条件に適するので1を返す
|
70
|
+
> ```
|
71
|
+
|
72
|
+
check_colorの戻り値によって、0か1を返すのではありませんか?
|
73
|
+
|
74
|
+
> ```c
|
75
|
+
> int savecount;
|
76
|
+
> ```
|
77
|
+
|
78
|
+
グローバル変数を使っていることに不安を覚えました。
|
79
|
+
-1 か判定してますけど、どんなときに -1 になりますか?
|
80
|
+
|
81
|
+
|
2
コードのバグ修正
test
CHANGED
@@ -57,7 +57,7 @@
|
|
57
57
|
}
|
58
58
|
|
59
59
|
int setten(struct rb_node *t, int count){//条件3、左右不一致なら-1
|
60
|
-
if (t==NULL) return
|
60
|
+
if (t==NULL) return count;
|
61
61
|
int setten_left = setten(t->left, 0);
|
62
62
|
if (setten_left==-1 || setten_left!=setten(t->right, 0)) return -1;
|
63
63
|
return count + t->black + setten_left;
|
1
修正版ソースコードを添付
test
CHANGED
@@ -8,6 +8,8 @@
|
|
8
8
|
|
9
9
|
check_colorの戻り値によって、0か1を返すのではありませんか?
|
10
10
|
|
11
|
+
ソースコードに手を入れてみました。
|
12
|
+
|
11
13
|
> ```c
|
12
14
|
> int savecount;
|
13
15
|
> ```
|
@@ -15,4 +17,62 @@
|
|
15
17
|
グローバル変数を使っていることに不安を覚えました。
|
16
18
|
-1 か判定してますけど、どんなときに -1 になりますか?
|
17
19
|
|
20
|
+
```c
|
21
|
+
#include<stdio.h>
|
22
|
+
#include<stdlib.h>
|
18
23
|
|
24
|
+
char buf[128];
|
25
|
+
struct map { int id; char name[32];};
|
26
|
+
typedef struct map datatype; /* ← 格納するデータは構造体 student */
|
27
|
+
struct rb_node { datatype data; struct rb_node *left, *right; int black; };
|
28
|
+
|
29
|
+
struct rb_node* get_rbtree() {
|
30
|
+
struct rb_node *t;
|
31
|
+
char c;
|
32
|
+
if(fgets(buf,sizeof(buf),stdin)==NULL || buf[0]=='.'){
|
33
|
+
/* ドットだけなら葉 (NULL) を返す */
|
34
|
+
return NULL;
|
35
|
+
} else {
|
36
|
+
/* ドットでなければ節点を表す構造体のアドレス t を用意 */
|
37
|
+
t = (struct rb_node*)malloc(sizeof(struct rb_node));
|
38
|
+
sscanf(buf,"[%c]%d,%[^,]",&c,&t->data.id,t->data.name);
|
39
|
+
t->black = c=='b';
|
40
|
+
t->left = get_rbtree(); t->right = get_rbtree();
|
41
|
+
return t;
|
42
|
+
}
|
43
|
+
}
|
44
|
+
|
45
|
+
int is_red(struct rb_node *t){
|
46
|
+
return t != NULL && !t->black;
|
47
|
+
}
|
48
|
+
|
49
|
+
int check_color(struct rb_node *t){//条件
|
50
|
+
//赤い節点の子が赤ならば条件に反するので0を返す
|
51
|
+
if(is_red(t) && (is_red(t->left) || is_red(t->right))) return 0;
|
52
|
+
//左右も同様に調べる
|
53
|
+
if (t->left && check_color(t->left)==0) return 0;
|
54
|
+
if (t->right && check_color(t->right)==0) return 0;
|
55
|
+
//条件に適するので1を返す
|
56
|
+
return 1;
|
57
|
+
}
|
58
|
+
|
59
|
+
int setten(struct rb_node *t, int count){//条件3、左右不一致なら-1
|
60
|
+
if (t==NULL) return 0;
|
61
|
+
int setten_left = setten(t->left, 0);
|
62
|
+
if (setten_left==-1 || setten_left!=setten(t->right, 0)) return -1;
|
63
|
+
return count + t->black + setten_left;
|
64
|
+
}
|
65
|
+
|
66
|
+
int is_rbtree(struct rb_node *t) {//赤黒木なら1を返す
|
67
|
+
int condition2 = check_color(t)==1;
|
68
|
+
int condition3 = setten(t, 0)!=-1;
|
69
|
+
return condition2 && condition3; //条件2,3に適するならば1、さもなくば0
|
70
|
+
}
|
71
|
+
|
72
|
+
int main() {
|
73
|
+
struct rb_node *t = get_rbtree();
|
74
|
+
printf("%s.\n", is_rbtree(t) ? "Yes" : "No");
|
75
|
+
return 0;
|
76
|
+
}
|
77
|
+
```
|
78
|
+
|