graph-theory - 8 個の黒いノードと 12 個の赤いノードを持つ RB ツリーを描画できますか?

Question

ここで、stackoverflow で同様の質問を見ましたが、(明らかに) 回答がありませんでした。

5 つの RB ツリーのいずれも無効にすることなく、そのようなツリー (8 つの黒いノードと 12 の赤いノード) を構築しようとすることができます (ただし、これまでのところ、それを行うことはできませんでした)。

1. ノードは赤または黒のいずれかです
2. 根元が黒い
3. 葉っぱが全部黒い
4. すべての赤いノードの両方の子は黒です
5. 特定のノードからその子孫の葉のいずれかへのすべての単純なパスには、同じ数の黒いノードが含まれます。

しかし、私はよりエレガントな答えに本当に興味があります(それが機能するかどうか試してみる以外に)。

編集：葉が黒としてカウントされる場合、そのようなツリーを構築することは不可能であることは明らかです. しかし、葉が黒いノードとしてカウントされない場合はどうでしょうか (8 つの非葉ノード)。

Answer 1

ルール 3 と 4 から、赤のノードをツリーに追加すると必然的に黒のノードが追加されるため、黒のノードよりも赤のノードを増やすことはできません。これは、rb ツリーの葉をノードとしてカウントする場合です (定義ではそうです)。