0

火曜日に中間試験があるのですが、赤黒木を理解するのに苦労しています。木がバランスが取れていることをどのように知ることができますか? 私はそれが正しい量の黒いノードと黒い深さと関係があることを知っています. しかし、私はそれをよく理解していません。ツリーの回転はこれに基づいているため、これを知る必要があります。誰かが段階的な説明を提供できれば、それは素晴らしいことです。ありがとう！

4

1 に答える 1

0

赤黒木のルールは次のとおりです。

  • 根元が黒い
  • nil ノードは黒 (省略される場合もあります)
  • 赤のノードは赤の子を持つことはできません
  • ルートからすべての葉へのパスには、同じ数の黒いノードが含まれています

したがって、あなたが参照しているルールは、私が想定する最後のルールです。木を描く別の言い方：黒のリンクが垂直で赤のリンクが水平の赤黒の木を表すと、すべての葉が同じレイヤーになります。

ツリーがこれら 4 つのルールに従う場合、それは有効な赤黒ツリーです。ルール 1 と 2 は簡単に修正できます。ツリーがルール 3 に従わない場合はコードレッド違反であり、ルール 4 に従わない場合はブラック違反と呼ばれます。

以下の例では、4 番目のルールが守られていないため、2 つのツリーに黒い違反が含まれています。

        2,B                   2,B 

       /   \                 /   \ 

     1,B   0,R           1,B      6,B  

                        /        /   \   

                       0,B      4,R   8,R

赤黒木が有効かどうかを判断することに関心がある場合は、いくつかを描画して、それらが規則を尊重しているかどうかを確認する必要があります。操作を理解する必要がある場合は、いくつかのチュートリアルを見る必要があります。インターネットにはたくさんあります。

いずれにせよ、赤黒木に関する素晴らしいチュートリアルがここにあります: http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx

興味がない場合は、実装の部分をスキップできますが、このように機能する理由を説明するルール、表現、およびアルゴリズムについて説明します。

お役に立てれば。

于 2016-05-16T01:32:39.660 に答える