13

ウィキの定義は正確ではないようです:

http://en.wikipedia.org/wiki/Red-black_tree#Properties

すべてのノードが黒いツリーは赤黒いツリーですか?

アップデート

rbtree の定義はそれほど厳密ではありませんが、黒のノードの子を赤または黒のどちらで出力するかをどのように決定すればよいでしょうか?

4

7 に答える 7

8

赤黒木は、単純に2-3-4 木の二分木表現です。赤黒ツリーの赤いノードは、類似の 2-3-4 ツリーの親ノードの一部に対応します。例えば：

           [black 5]
          /         \
      [red 3]     [black 6]
     /       \
[black 2] [black 4]

は 2-3-4 ツリーの表現です

    [3 | 5]
   /   |   \
 [2]  [4]  [6]

赤黒木に黒いノードしかない[3 | 5]場合、それは 2-3-4 ツリーを表し、3 ノード (例のように) や 4 ノードではなく、2 ノード (単一エントリ) のみを表すことを意味します。これは基本的に単純な二分探索木であることに注意してください。

于 2011-06-20T03:58:09.303 に答える
8

はい、すべてのノードが黒のツリーは、赤黒ツリーになる可能性があります。ツリーは完全なバイナリ ツリー (すべての葉が同じ深さまたは同じレベルにあり、すべての親が 2 つの子を持つ) である必要があるため、黒の高さがそのツリーの高さ と等しい唯一のツリーです。

于 2013-04-04T01:08:37.330 に答える
3

すべてのノードが黒の適切な赤黒ツリーを作成することは可能です。自明なことですが、ノードが 1 つだけの RBTree、またはルートの直接の子であるリーフ ノードのみを持つ RBTree は、すべてバック ノードになります。

于 2011-06-20T03:53:48.227 に答える
2

ノードを赤と黒のどちらで印刷するかを決定するという質問の 2 番目の部分に答えるために、その情報は各ノードに保存されます。

典型的な二分探索木では、各ノードには値、左ポインター、および右ポインター (および場合によっては親ポインター) が含まれます。赤黒ツリーでは、各ノードにはこれらすべてのものに加えて、このノードが赤か黒かを示す追加のフィールドが含まれます。挿入や削除など、ツリーに対するさまざまな操作は、この色情報を一貫した方法で維持する役割を果たします。

色の付いていないツリーが与えられ、ノードの色を選択するように言われることはありません (おそらく宿題や試験の問題を除いて)。

于 2011-06-20T18:56:34.730 に答える
1

はい、すべて黒のノードを持つツリーは、赤黒のツリーになる可能性があります。等しい黒深度プロパティを維持するために、そのようなツリーは完全に塗りつぶされたツリーでなければならないことを証明できます。

そのような小さなツリーを構築することにより、すべての黒いノードを持つツリーが赤黒いツリーになることを自分で証明できます。例えば：

                            2,black
                      1,black      3,black

このツリーにはすべて黒のノードがあり、すべての条件を満たしています。ルートが親として nil を持ち、両方のリーフ ノードが両方の子を nil として持っていると仮定します。これが役立つことを願っています。

于 2012-03-27T12:40:58.470 に答える
0

はい。ただし、すべてのノードが赤の赤黒ツリーには当てはまりません。そのようなツリーは無効です。どのノードを黒にする必要があるかについては制限があります。たとえば、葉のノードは黒である必要があり、赤のノードの子は両方とも黒である必要があります。

于 2011-06-20T03:55:09.723 に答える