回答編集履歴

9

count_black関数のcount引数が不要だったので削除

2022/03/27 10:07

投稿

shiracamus
shiracamus

スコア5406

test CHANGED
@@ -40,16 +40,16 @@
40
40
  return true;
41
41
  }
42
42
 
43
- int count_black(struct rb_node *t, int count){//条件3、左右不一致なら-1
43
+ int count_black(struct rb_node *t){//条件3、左右不一致なら-1
44
- if (t == NULL) return count;
44
+ if (t == NULL) return 0;
45
- int left_black = count_black(t->left, 0);
45
+ int left_black = count_black(t->left);
46
- if (left_black == -1 || left_black != count_black(t->right, 0)) return -1;
46
+ if (left_black == -1 || left_black != count_black(t->right)) return -1;
47
- return count + t->black + left_black;
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, 0) != -1;
52
+ return is_order_ok(t) && count_black(t) != -1;
53
53
  }
54
54
 
55
55
  int main() {

8

真偽値を返す関数の戻り値の型を bool に変更

2022/03/27 09:59

投稿

shiracamus
shiracamus

スコア5406

test CHANGED
@@ -26,11 +26,11 @@
26
26
  }
27
27
  }
28
28
 
29
- int is_red(struct rb_node *t){
29
+ bool is_red(struct rb_node *t){
30
30
  return t != NULL && !t->black;
31
31
  }
32
32
 
33
- int is_order_ok(struct rb_node *t){//条件2
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
- int is_rbtree(struct rb_node *t) {//赤黒木なら1を返す
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 に変更

2022/03/27 09:55

投稿

shiracamus
shiracamus

スコア5406

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
- //赤い節点の子が赤ならば条件に反するので0を返す
34
+ //赤い節点の子が赤ならば条件に反するのでfalseを返す
34
- if(is_red(t) && (is_red(t->left) || is_red(t->right))) return 0;
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) == 0) return 0;
37
+ if (t->left && !is_order_ok(t->left)) return false;
37
- if (t->right && is_order_ok(t->right) == 0) return 0;
38
+ if (t->right && !is_order_ok(t->right)) return false;
38
- //条件に適するので1を返す
39
+ //条件に適するのでtrueを返す
39
- return 1;
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に適するならば1、さもなくば0
51
+ //条件2,3に適するならばtrue、さもなくばfalse
51
52
  return is_order_ok(t) && count_black(t, 0) != -1;
52
53
  }
53
54
 

6

変数名・関数名見直し

2022/03/27 09:44

投稿

shiracamus
shiracamus

スコア5406

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 check_color(struct rb_node *t){//条件
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 && check_color(t->left)==0) return 0;
36
+ if (t->left && is_order_ok(t->left) == 0) return 0;
37
- if (t->right && check_color(t->right)==0) return 0;
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 setten(struct rb_node *t, int count){//条件3、左右不一致なら-1
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 setten_left = setten(t->left, 0);
44
+ int left_black = count_black(t->left, 0);
45
- if (setten_left==-1 || setten_left!=setten(t->right, 0)) return -1;
45
+ if (left_black == -1 || left_black != count_black(t->right, 0)) return -1;
46
- return count + t->black + setten_left;
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
- int is_count_ok = setten(t, 0)!=-1;
50
+ //条件2,3に適するならば1、さもなくば0
52
- return is_order_ok && is_count_ok; //条件2,3に適するならば1、さもなくば0
51
+ return is_order_ok(t) && count_black(t, 0) != -1;
53
52
  }
54
53
 
55
54
  int main() {

5

変数名見直し

2022/03/27 09:11

投稿

shiracamus
shiracamus

スコア5406

test CHANGED
@@ -47,9 +47,9 @@
47
47
  }
48
48
 
49
49
  int is_rbtree(struct rb_node *t) {//赤黒木なら1を返す
50
- int condition2 = check_color(t)==1;
50
+ int is_order_ok = check_color(t)==1;
51
- int condition3 = setten(t, 0)!=-1;
51
+ int is_count_ok = setten(t, 0)!=-1;
52
- return condition2 && condition3; //条件2,3に適するならば1、さもなくば0
52
+ return is_order_ok && is_count_ok; //条件2,3に適するならば1、さもなくば0
53
53
  }
54
54
 
55
55
  int main() {

4

比較演算子の空白を削除して統一

2022/03/27 09:05

投稿

shiracamus
shiracamus

スコア5406

test CHANGED
@@ -26,7 +26,7 @@
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
32
  int check_color(struct rb_node *t){//条件

3

追記の位置がおかしかったので修正

2022/03/27 09:00

投稿

shiracamus
shiracamus

スコア5406

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

コードのバグ修正

2022/03/27 05:37

投稿

shiracamus
shiracamus

スコア5406

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 0;
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

修正版ソースコードを添付

2022/03/27 04:59

投稿

shiracamus
shiracamus

スコア5406

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
+