Q&A
とりあえず、「根から葉にたどり着くまでに通る黒い節点の数がすべて同じ」を直接調べるのではなくまずは「赤黒木の部分木は必ず赤黒木か？」あたりから考えてみてはどうでしょうか。学校の課題っぽいので。
今赤黒木かどうかを判定する関数を作成してまして、ｔの指す節点を根とする二分探索木に対し、赤黒木だったら1を返し、赤黒木でなければ０を返すという関数を実装したいのですが、赤黒木を満たすための条件である「根から葉にたどり着くまでに通る黒い節点の数がすべて同じ」という部分を実装させることが出来ません。
他の条件の「葉は必ず黒」、「赤の節点の子は必ず黒」というのは書けますが上記の所のみ思い浮かばないです。どうしたらいいでしょうか？
C
1int rbtree(struct node *t){ 2/*関数*/ 3}
回答2件
0
とりあえず愚直にやる方法だけ。もっと別にカッコイイ実装があるかもしれませんが。
「根から葉にたどり着くまでに通る黒い節点の数がすべて同じ」ってことは
「グラフのすべての部分木において(部分木の)根から部分木のすべての葉にたどり着くまでに通る黒い節点の数がすべて同じ」と等価です。これは必要条件と十分条件を証明する必要がありますが省きます。
あとはこれを再帰的に深さ優先探索しながら確認すればいいです。再帰を行う関数は部分木の高さと部分木が条件を満たしているかどうかと二つの情報を返す必要がある ので、そこでちょいと工夫が必要でしょう。
なお、赤黒木を使いたくて実装しているのでしたら、自分で実装せずに既存のライブラリを使うのが安全だとはおもいます。
投稿2018/02/06 02:33
総合スコア702
BlackEyeさんコメントから「赤ノードの子供が黒」なのは真だが「黒ノードの子供が葉以外の場合、そのノードが赤なのか黒なのか」はなにかの判断基準がない限り一意には決まらないと解釈しました。そういう意味で「黒い節点かどうか」を決めること自体が問題のポイントなのかなと思いました。それについはいかがでしょうか？
赤黒木というのは「各ノードは赤か黒の色をもつ」ということなので、各ノードが赤か黒かは与えられたデータに含まれているのでは？
質問者さんの想定は「任意の二進木が与えられたときその木が赤黒木として成立しているかを判定したい」ということに見えました。ゆえに自分は各ノードに「赤か黒か」は与えられていないと想定しました。
その点はいかがですか？＞質問者さん。
「(適切に赤黒を割り当てれば)赤黒木として成立しうるか」だと難度が上がりますね。
制約を満たし得る色付けアルゴリズムは考えられそうではあるのですが、なんとなく「そんなことをしなくても単純な方法で判定する方法がある」なんて落ちになってそうな予感が・・・。
黒の節点の数が同じことを証明に使うのではなく単純に各葉についてルートからの節点の数の最大と最小を求めてそれが制約（最大は最小の2倍を超えない）を満たしているかという判定でよいような気もします。
0
訂正：
指摘コメントをいただいたにも限らず、自分が間違いを犯していることになかなか気づけませんでした。お二人の指摘の意味はwikiを落ち着いて読んでみてようやく気づけました。以下の回答は全然ダメですね・・・失礼いたしました。
元の回答
葉以外のノードは必ず親と違う色だと思います。つまり根が黒とすればその一つ下がノードなら必ず赤ノード、その下がノードなら必ず黒ノードという具合です。
ゆえに以下の(A)は(B)と同じと考えてよいと思います。
(A) 根から葉までの黒のノードの数
(B) floor((根から葉までの全ノードの数+1)/2)
ですから「根から葉までの全ノードの数」を数えつつ、葉に到達したら(B)を計算し、その値が全ての葉について等しいかどうかをチェックすればよいと思います。
投稿2018/01/19 15:51
編集2018/02/05 07:54総合スコア18404
同じ講義を受けてる人のその演習の答えを求める質問なので答えづらいですが、赤黒木において「葉以外のノードは必ず親と違う色」というのは間違いです。黒いノードの親が黒でもよいので、(A)と(B)は等しくなりません。
自分は「葉はノードとはみなさない」という前提でコメントしています。Wikipediaの例をみてもそのようになっているように見えます。ノードの数には葉は含めないのです。そうした細かな点を明記すべきだったですね。
wikipediaを根拠に挙げても不毛なのですが、『この記事においては、今まで説明したように「空の葉」（nil leaf、null leaf）を用い、葉はデータをもたずただ木の終端を意味するだけのノードであるとした。』と、葉もノードであるかのようにも書いてありますね。
コメントありがとうございます。確かにそう書いてありますね！
自分がWikipediaの説明を読んだ時には感じませんでしたが質問者さんの文章、wikipediaの説明、自分がおいた前提に違いがあるため読み手を混乱させてしまうコメント内容になっていますね。申し訳ないです。
失礼しました。BlackEyeさんのa_saitohさんの指摘の本当の意味にようやく気付きました。
葉以外の黒ノードも連続していることはあり、wikiに載っている条件を全て満たすような木になりえるかどうかを判定する点が肝だったのですね。自分の回答は・・・全然ダメですね！
あなたの回答
tips
プレビュー
