赤黒 - 建設

Question

最近、私は検索ツリーを通り抜けていて、赤黒の木に遭遇しました。私を混乱させる点は、RBツリーで、ルートノードは黒である必要があります。これで、入ってくるノードが赤または黒い色を想定するかどうかをどのように判断しますか。

私はwikiの記事を読みましたが、これに対する解決策は見つかりませんでした。私は間違っているかもしれませんが、誰かが正確な素材を私に導くことができれば、私は幸せです。

編集]それは、たとえば、私のキーが{7、2、4、1、9、10、8}の場合です

ここで7はルートで、黒い色を想定していますが、2は何色を想定していますか？どうやってそれを決定しますか？そして、他のノードが想定する色をどのように決定しますか？

                                  7 - (Black)
                   2                              9
           1                   4        8                    10
        NIL   NIL          NIL  NIL   NIL  NIL            NIL  NIL

ノードの色を赤または黒であると決定するランダムなトスがありますか。または、他のプロセスですか。

ありがとうございました。

Answer 1

MITオープンコースウェアの赤黒樹木に関する講義を見てください。

http://ocw.mit.edu/ocwweb/electrical-engineering-and-computer-science/6-046jfall-2005/videolectures/

私はそれらがとても役に立つことがわかりました。

私が正しく覚えている場合、あなたは常に新しいノードをブラックノードとして挿入し、必要な修正（再塗装および/または回転）に進みます

Answer 2

着信ノードを赤色に色付けする必要があります。なぜなら、新しく挿入されたノードのルートパスのすべての葉の高さの高さよりも黒に着信ノードを色にすると、すべてのルートからリーフパスが必要なRBツリープロパティに違反するものによって増加するためです。同じ数の黒いノードが含まれています。これを参照してくださいRBツリーの挿入にもっと洞察したい場合 http://www.youtube.com/watch?v=6qokk_pcv3u