algorithm - 赤いノードのない赤黒木を作ることはできますか？

Question

赤黒木には少なくとも1つの赤いノードが必要かどうか疑問に思います。また、BSTが与えられた場合、それをRBTに変換できる場合、このツリーを赤黒木に変換する独自の方法はありますか？

Answer 1

赤黒木のプロパティをひと目見ると、ノードを赤にする必要がないことがわかります。赤いノードが発生する唯一の方法は、プロパティ5を使用することです。

特定のノードからその子孫リーフへのすべての単純なパスには、同じ数の黒いノードが含まれています。

このプロパティは、完全な二分木でも満たされるため、黒ノードのみを持つすべての完全な二分探索木も赤黒木になります。（ただし、教科書の赤黒木アルゴリズムがこれらを生成するかどうかはわかりません。）

また、BSTが与えられた場合、それをRBTに変換できる場合、このツリーを赤黒木に変換する独自の方法はありますか？

任意のBSTに単一の一意のRBTはありません。非常に浅い木を除いて、常に複数の同等のRBTがあります。