赤黒木の判定について

Question

実現したいこと

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

発生している問題

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

該当のソースコード

#include<stdio.h>
#include<stdlib.h>
char buf[128];
struct map { int id; char name[32];};
typedef struct map datatype; /* ← 格納するデータは構造体 student */
struct rb_node { datatype data; struct rb_node *left, *right; int black; };

struct rb_node* get_rbtree() {
  struct rb_node *t;
  char c;
/* ドットだけなら葉 (NULL) を返す */
  if(fgets(buf,sizeof(buf),stdin)==NULL || buf[0]=='.')
    return NULL;
  else {
/* ドットでなければ節点を表す構造体のアドレス t を用意 */
    t = (struct rb_node*)malloc(sizeof(struct rb_node));
/* 色を表す文字を c に、id、名前を t->data に格納 */
    sscanf(buf,"[%c]%d,%[^,]",&c,&t->data.id,t->data.name);
/* 色の文字が b なら 1、r なら 0 */
    t->black = (c=='b');
/* 左の子を t->left に、右の子を t->right に格納 */
    t->left = get_rbtree(); t->right = get_rbtree();
/* t を返す */
    return t;
  }
}
int is_red(struct rb_node *t){
    return(t != NULL && !t->black);
}

int check_color(struct rb_node *t){//条件
  if(is_red(t) == 1){
        if(is_red(t->left) == 1 || is_red(t->right) == 1){//赤い節点の子が赤ならば
            return 0;//条件に反するので0を返す
        }
  }
  check_color(t->left);
  check_color(t->right);
  return 1;//条件に適するので1を返す
}

int savecount;
int setten(struct rb_node *t, int count){//条件3
   count += t->black;
    if(!t->left && !t->right){ 
        if(savecount==-1){
            savecount = count;
            return 1;
        }else if(savecount != count){
            return 0;
        }else{
            return 1;
        }
    }
    if(t->left){
        if(setten(t->left,count)==0){
            return 0;
        }
    }
    if(t->right){
        if(setten(t->right,count)==0){
            return 0;
        }
    }
    return 1;
}

int is_rbtree(struct rb_node *t) {//赤黒木なら1を返す
  int a = 1;
  int b = 1;
  a = check_color(t);
  b = setten(t, 0);
  if(a == 1 && b == 1){//条件2,3に適するならば
      return 1;
  }else{//条件2,3に反するものがあるならば
      return 0;
  }
}

int main() {
    struct rb_node *t = get_rbtree();
    if(is_rbtree(t)) printf("Yes.\n");
    else printf("No.\n");
    return 0;
}

入出力例

入力
[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()に違反)

Comments

[mizutani.cs]

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

[y_waiwai]

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

[mizutani.cs]

はい、お待ちください

[shiracamus]

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

[mizutani.cs]

わかりました

[mizutani.cs]

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

[thkana]

クラスメイトかしら? ご参考まで。
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10259174745

[jimbe]

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

[mizutani.cs]

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

[jimbe]

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

[mizutani.cs]

はい。

[jimbe]

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

[mizutani.cs]

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

Answer 1

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

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

char buf[128];
struct map { int id; char name[32];};
typedef struct map datatype; /* ← 格納するデータは構造体 student */
struct rb_node { datatype data; struct rb_node *left, *right; int black; };

struct rb_node* get_rbtree() {
  struct rb_node *t;
  char c;
  if(fgets(buf,sizeof(buf),stdin) == NULL || buf[0] == '.'){
    /* ドットだけなら葉 (NULL) を返す */
    return NULL;
  } else {
    /* ドットでなければ節点を表す構造体のアドレス t を用意 */
    t = (struct rb_node*)malloc(sizeof(struct rb_node));
    sscanf(buf,"[%c]%d,%[^,]",&c,&t->data.id,t->data.name);
    t->black = c == 'b';
    t->left = get_rbtree(); t->right = get_rbtree();
    return t;
  }
}

bool is_red(struct rb_node *t){
  return t != NULL && !t->black;
}

bool is_order_ok(struct rb_node *t){//条件2
  //赤い節点の子が赤ならば条件に反するのでfalseを返す
  if(is_red(t) && (is_red(t->left) || is_red(t->right))) return false;
  //左右の葉に到達するまで同様に調べる
  if (t->left && !is_order_ok(t->left)) return false;
  if (t->right && !is_order_ok(t->right)) return false;
  //条件に適するのでtrueを返す
  return true;
}

int count_black(struct rb_node *t){//条件3、左右不一致なら-1
  if (t == NULL) return 0;
  int left_black = count_black(t->left);
  if (left_black == -1 || left_black != count_black(t->right)) return -1;
  return t->black + left_black;
}

bool is_rbtree(struct rb_node *t) {//赤黒木なら1を返す
  //条件2,3に適するならばtrue、さもなくばfalse
  return is_order_ok(t) && count_black(t) != -1;
}

int main() {
  struct rb_node *t = get_rbtree();
  printf("%s.\n", is_rbtree(t) ? "Yes" : "No");
  return 0;
}

最初のコメント：

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

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

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

int savecount;

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

Comments

[mizutani.cs]

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

[shiracamus]

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

[mizutani.cs]

すいません。提示してくださったプログラムで、編集前の
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]

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

[mizutani.cs]

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

[mizutani.cs]

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

[shiracamus]

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

[mizutani.cs]

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

[shiracamus]

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

[mizutani.cs]

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

[mizutani.cs]

編集前の
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]

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

[shiracamus]

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

[mizutani.cs]

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