1

最近、私は検索ツリーを調べていて、赤黒の木に遭遇しました。私を混乱させるポイントは、rb ツリーでは、ルート ノードは黒である必要があります。それで問題ありません。着信ノードが赤と黒のどちらの色を想定しているかをどのように判断しますか? .

ウィキの記事を読みましたが、これに対する解決策は見つかりませんでした。間違っているかもしれませんが、誰かが正確な資料を案内してくれると嬉しいです.

[編集] たとえば、私のキーが {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

ノードの色を赤または黒に決定するランダム トスはありますか。それとも他のプロセスですか？

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

4

2 に答える 2

1

MIT オープン コースウェアの red-black trees に関する講義をご覧ください。

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/

とても役に立ちました。

私の記憶が正しければ、常に新しいノードを黒いノードとして挿入してから、必要な修正 (再描画および/または回転) に進みます。

于 2010-04-04T01:41:05.843 に答える
1

着信ノードを赤く着色する必要があります。着信ノードを黒く色付けすると、新しく挿入されたノードのすべてのリーフからルートへのパスの高さが 1 だけ増加し、すべてのルートからリーフへのパスがなければならない RB ツリー プロパティに違反するためです。 RB ツリーの挿入についてさらに詳しく知りたい場合は、これを参照してください http://www.youtube.com/watch?v=6QOKk_pcv3U

于 2014-10-08T13:08:12.250 に答える