algorithm - レッドブラックツリーの質問

Question

赤黒の木のノードは、赤と黒の子を 1 つずつ持つことができますか?

私は次のツリーを持っています。ここでは色だけを指定しました。リーフ ノードは無視されます。

                   B
           R               B
       B       B       R       R 
     R   R       R

Answer 1

はい、ノードは異なる色の子を持つことができます。たとえば、RBツリーに関するMathWorldの記事の最上部にある図を参照してください。RBツリーのすべての要件を満たし、そのノードの1つに異なる色の子があることを確認できます。として、そのことについては、あなたが与えた例を行います。

Answer 2

Haskellでデータ構造を学習するという文脈での真っ黒な木に関する良い記事があります。

http://scientopia.org/blogs/goodmath/2009/11/30/advanced-haskell-data-structures-red-black-trees/

それが与えるRBツリーの基準はかなり明確です。赤いノードの子は黒である必要がありますが、黒いノードの子は指定されていません。重要な点は、特定のノードからその下のリーフまでのすべてのパスに、同じ数の黒いノードが必要であるということです。ツリーを見ると、ルートから下のすべてのパスに1つの黒いノード（ルートを数えると2つ）があるので、問題ありません。