質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.02%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

赤黒木の判定について

mizutani.cs
mizutani.cs

総合スコア4

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

1回答

0グッド

0クリップ

666閲覧

投稿2022/03/27 01:21

編集2022/03/27 01:49

実現したいこと

赤黒木かどうかの判定基準である「赤い節点の子は黒い節点」と「根から葉までの黒い節点の数が一致」という二つの条件をそれぞれ判定するプログラム「check_color」と「setten」の作成

発生している問題

以下のように作成したところ、どのような木を入力してもcheck_color()は1,setten()は0を毎回出力するようになってしまっています。どこがおかしいのでしょうか。

該当のソースコード

C

1#include<stdio.h> 2#include<stdlib.h> 3char buf[128]; 4struct map { int id; char name[32];}; 5typedef struct map datatype; /* ← 格納するデータは構造体 student */ 6struct rb_node { datatype data; struct rb_node *left, *right; int black; }; 7 8struct rb_node* get_rbtree() { 9 struct rb_node *t; 10 char c; 11/* ドットだけなら葉 (NULL) を返す */ 12 if(fgets(buf,sizeof(buf),stdin)==NULL || buf[0]=='.') 13 return NULL; 14 else { 15/* ドットでなければ節点を表す構造体のアドレス t を用意 */ 16 t = (struct rb_node*)malloc(sizeof(struct rb_node)); 17/* 色を表す文字を c に、id、名前を t->data に格納 */ 18 sscanf(buf,"[%c]%d,%[^,]",&c,&t->data.id,t->data.name); 19/* 色の文字が b なら 1、r なら 0 */ 20 t->black = (c=='b'); 21/* 左の子を t->left に、右の子を t->right に格納 */ 22 t->left = get_rbtree(); t->right = get_rbtree(); 23/* t を返す */ 24 return t; 25 } 26} 27int is_red(struct rb_node *t){ 28 return(t != NULL && !t->black); 29} 30 31int check_color(struct rb_node *t){//条件 32 if(is_red(t) == 1){ 33 if(is_red(t->left) == 1 || is_red(t->right) == 1){//赤い節点の子が赤ならば 34 return 0;//条件に反するので0を返す 35 } 36 } 37 check_color(t->left); 38 check_color(t->right); 39 return 1;//条件に適するので1を返す 40} 41 42int savecount; 43int setten(struct rb_node *t, int count){//条件3 44 count += t->black; 45 if(!t->left && !t->right){ 46 if(savecount==-1){ 47 savecount = count; 48 return 1; 49 }else if(savecount != count){ 50 return 0; 51 }else{ 52 return 1; 53 } 54 } 55 if(t->left){ 56 if(setten(t->left,count)==0){ 57 return 0; 58 } 59 } 60 if(t->right){ 61 if(setten(t->right,count)==0){ 62 return 0; 63 } 64 } 65 return 1; 66} 67 68int is_rbtree(struct rb_node *t) {//赤黒木なら1を返す 69 int a = 1; 70 int b = 1; 71 a = check_color(t); 72 b = setten(t, 0); 73 if(a == 1 && b == 1){//条件2,3に適するならば 74 return 1; 75 }else{//条件2,3に反するものがあるならば 76 return 0; 77 } 78} 79 80int main() { 81 struct rb_node *t = get_rbtree(); 82 if(is_rbtree(t)) printf("Yes.\n"); 83 else printf("No.\n"); 84 return 0; 85}

入出力例

入力
[b]10567,nagano
[r]10234,tokyo
[b]10123,kanagawa
.
.
[b]10345,chiba
.
[r]10456,aomori
.
.
[b]10678,ishikawa
.
.
出力
Yes.

入力
[b]10567,nagano
[r]10234,tokyo
[r]10123,kanagawa
.
.
.
[r]10456,aomori
.
.
出力
No.(check_colorに違反)

入力
[b]chiba
[b]kanagawa
.
[r]tokyo
.
.
[b]10678,ishikawa
[b]10456,aomori
.
[r]10567,nagano
.
.
[r]10890,kumamoto
.
.
出力
No.(setten()に違反)

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

mizutani.cs

2022/03/27 01:24

setten()に渡すcountには、main関数から0を渡しています。
y_waiwai

2022/03/27 01:33

コードは全部のせましょう
mizutani.cs

2022/03/27 01:34

はい、お待ちください
shiracamus

2022/03/27 01:41

入力データ例と期待する結果をいくつか、質問に追記していただけませんか?
mizutani.cs

2022/03/27 01:55

違反理由は出力しないですが参考に載せました。
jimbe

2022/03/27 08:50 編集

ご提示のコードを実行しても入出力例のように出来ないみたいですけど。
mizutani.cs

2022/03/27 08:42 編集

入出力例は、あくまで「本来こうなるべき」という意味であって提示したプログラムです。勘違いさせるような記述をしてしまい申し訳ありません。
jimbe

2022/03/27 10:22

入出力例の最初の Yes になるはずの入力では、その入力によってどのようなツリーが出来ているか確認されていますでしょうか。
jimbe

2022/03/27 13:12

ご提示の get_rbtree を使って出来たツリーを見ると、 check_color 違反になる構造になってしまうのですが…。
mizutani.cs

2022/03/27 13:35

ごめんなさい、少しいじったget_rbtreeを提示したためどこかがおかしくなっているのだと思います。shiracamusさんが作成したものを使っていただければ正しく動作すると思います。すみませんでした。

回答1

1

ベストアンサー

追記: ソースコードに手を入れてみました。

c

1#include<stdio.h> 2#include<stdlib.h> 3#include<stdbool.h> 4 5char buf[128]; 6struct map { int id; char name[32];}; 7typedef struct map datatype; /* ← 格納するデータは構造体 student */ 8struct rb_node { datatype data; struct rb_node *left, *right; int black; }; 9 10struct rb_node* get_rbtree() { 11 struct rb_node *t; 12 char c; 13 if(fgets(buf,sizeof(buf),stdin) == NULL || buf[0] == '.'){ 14 /* ドットだけなら葉 (NULL) を返す */ 15 return NULL; 16 } else { 17 /* ドットでなければ節点を表す構造体のアドレス t を用意 */ 18 t = (struct rb_node*)malloc(sizeof(struct rb_node)); 19 sscanf(buf,"[%c]%d,%[^,]",&c,&t->data.id,t->data.name); 20 t->black = c == 'b'; 21 t->left = get_rbtree(); t->right = get_rbtree(); 22 return t; 23 } 24} 25 26bool is_red(struct rb_node *t){ 27 return t != NULL && !t->black; 28} 29 30bool is_order_ok(struct rb_node *t){//条件2 31 //赤い節点の子が赤ならば条件に反するのでfalseを返す 32 if(is_red(t) && (is_red(t->left) || is_red(t->right))) return false; 33 //左右の葉に到達するまで同様に調べる 34 if (t->left && !is_order_ok(t->left)) return false; 35 if (t->right && !is_order_ok(t->right)) return false; 36 //条件に適するのでtrueを返す 37 return true; 38} 39 40int count_black(struct rb_node *t){//条件3、左右不一致なら-1 41 if (t == NULL) return 0; 42 int left_black = count_black(t->left); 43 if (left_black == -1 || left_black != count_black(t->right)) return -1; 44 return t->black + left_black; 45} 46 47bool is_rbtree(struct rb_node *t) {//赤黒木なら1を返す 48 //条件2,3に適するならばtrue、さもなくばfalse 49 return is_order_ok(t) && count_black(t) != -1; 50} 51 52int main() { 53 struct rb_node *t = get_rbtree(); 54 printf("%s.\n", is_rbtree(t) ? "Yes" : "No"); 55 return 0; 56}

最初のコメント:

とりあえず、気付いた点だけ。

C

1 check_color(t->left); 2 check_color(t->right); 3 return 1;//条件に適するので1を返す

check_colorの戻り値によって、0か1を返すのではありませんか?

c

1int savecount;

グローバル変数を使っていることに不安を覚えました。
-1 か判定してますけど、どんなときに -1 になりますか?

投稿2022/03/27 01:36

編集2022/03/27 10:07
shiracamus

総合スコア5394

mizutani.cs👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

mizutani.cs

2022/03/27 02:16

このcheck_colorだと、再帰して if(is_red(t) == 1){ if(is_red(t->left) == 1 || is_red(t->right) == 1){//赤い節点の子が赤ならば return 0;//条件に反するので0を返す } } に適する箇所があったときに0を返してプログラムを抜け出すということにはならないのでしょうか。
shiracamus

2022/03/27 03:07

赤の下に黒があって、その黒の下に赤があって、その赤の下が赤だったら 0 にしないといけないですよね? check_color(t->left) で自分の下をチェックしてますけど、その戻り値をチェックしてないので return 1 してしまいますよ。
mizutani.cs

2022/03/27 09:21

すいません。提示してくださったプログラムで、編集前の 1.if(is_red(t) && (is_red(t->left) || is_red(t->right))){ 2.if (t->left && check_color(t->left)==0) { 3.int condition2 = check_color(t)==1; の3つの箇所についてなのですが、それぞれどのような意味なのでしょうか。文がそのまま数字で表される?ような記述をしたことがなく分からないので教えていただきたいです。
shiracamus

2022/03/27 09:33

1.は元のコードで入れ子になっていたif文を1つにまとめただけです。 2.は左にノードがあれば、左のノード配下にも不成立がないか再帰的に調べます。赤->黒->赤->赤 とあったときに深い所まで調べないといけないですから。 3. はcheck_color関数から1が返ったときに正常だと判断しています。関数名が is_xxx であれば比較不要ですが、checkという関数名なので戻り値を比較しました。関数名にcheckという名前は使わない方がいいです。
mizutani.cs

2022/03/27 09:39

ありがとうございます。3についてはつまり、check_color関数から1が返ったときに正常だと判断してint condition2  =1として、違かった場合にはint condition2 = 0にするということでしょうか?
mizutani.cs

2022/03/27 09:44

そして1,2については言葉で表すと、 1.is_red(t)が1かつ「is_red(t->left) と is_red(t->right)のいずれかが1」ならば 2.t->leftにノードがあり、かつ左のノード配下に不適なものがあるならば ということでしょうか。
shiracamus

2022/03/27 09:46

そういうことです。 変数名と関数名を見直してみました。
mizutani.cs

2022/03/27 09:47

細かくありがとうございます。編集後のものも確認します。
shiracamus

2022/03/27 09:53

if 文を書くとき if ((count > 0) == 1) とは書かないですよね? 同様に、比較結果を代入した変数 や 比較結果を返す is_xxx 関数の戻り値 は、0 や 1 と比較しない方がいいですよ。
mizutani.cs

2022/03/27 09:56

確かにそうですね。プログラムの見易さも変わりそうですし気を付けてみます。
mizutani.cs

2022/03/27 11:45

編集前の int setten(struct rb_node *t, int count){//条件3、左右で黒い節点の数が不一致なら-1 if (t==NULL){ return count; } int setten_left = setten(t->left, 0); if (setten_left == -1 || setten_left != setten(t->right, 0)) { return -1; } return count + t->black + setten_left; } なのですが、 int setten_left = setten(t->left, 0); if (setten_left == -1 || setten_left != setten(t->right, 0)) { return -1; } return count + t->black + setten_left; の理屈は理解したのですが、自分で思いつけそうにないと思えてしまいました。何か「○○のように考えた」のような発想のヒントを教えてもらえますか?難しいと思うので、出来たらで...
mizutani.cs

2022/03/27 11:47

編集後のプログラムのboolは初めて見たのですがとても便利ですね。今回のプログラムでは指定した箇所のみを書くというものだったので使用できませんが、用法を覚えておきます。
shiracamus

2022/03/27 12:23 編集

発想は、左右にぶら下がっている黒の数が同じか確認するので、左と右と黒をそれぞれ数えて比較すればいいだろうというだけのことです。 どっちかが -1 なら比較するまでもなく不適合。 同じであれば自分が黒かどうかの数を加えて呼び出し元に返す。 基本的に、自分が目で追って数える方法をプログラムに落とし込むだけです。
mizutani.cs

2022/03/27 12:42

なるほど、ありがとうございます。

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。