8

最初にすべての赤黒条件を満たし、集合S内のすべての整数sに対して 1 つのノードを含む二分探索木があるとします。次に、新しいノードが必要です。aと言う(これはSにはない)。

この追加の結果は、リバランス後にユニークですか?

別の言い方をすれば、ノードを挿入した後に赤黒木を再調整する方法は 1 つだけですか?

証拠はありませんが（そして自信はほとんどありません）、それらは一意ではないと思います。私よりも知識のある人が私を啓発してくれるのではないかと思っています。

4

2 に答える 2

8

それらは一意ではありません。

簡単な証明は、ルートの色を変更できることを確認するなど、簡単なアルゴリズムの変更を行い、それがまだ有効である場合を提供することです。たとえば、次のようになります。

    1-B
   /  \
 0-R  2-R

add(3):

    1-B
   /  \
 0-B  2-B
        \
        3-R

しかし、新しいアルゴリズムは非常に簡単に生成できます

    1-R
   /  \
 0-B  2-B
        \
        3-R

ルートは別の色ですが、もちろん、ツリーは両方とも有効なRBツリーです。

これは少し些細なことのように思えるかもしれませんが、（些細なことではない証明が必要な場合は）アイデアを拡張して、ルート以上のものをチェックすることができます。O（1）レベルを深くチェックして、重要であるが有効な変更を行うことができます。これにより、同じ実行時間で2つの異なるアルゴリズムが生成されます。

たとえば、最初の10行が完全で黒であることを確認し、奇数行を赤に変更すると、追加の定数作業（つまり、O（1））と新しいアルゴリズムが生成されます。

これは単に非一意性の証拠であり、非一意性の量に制限されないことに注意する必要があります。つまり、このような些細なことで要点を証明できますが、より基本的な方法で異なるRBアルゴリズムへの扉が開かれたままになります。

于 2011-07-19T17:18:52.933 に答える
2

複数のアロリズムはありません。

この2つの提案から始めましょう：

  • 内部ノードが4つある赤黒木の数は3です。
  • 内部ノードが5つある赤黒木の数は8です。

ここで、4つの内部ノードの赤黒木にノードを追加するための独自のアルゴリズムがあると想像してください。その場合、アルゴリズムは1つの結果につながるため、5つの内部ノードを持つ3つの赤黒木のみが存在するはずです。

内部ノードが5つある赤黒木の数が8であるため、これはばかげています。

（ 鳩の巣原理を参照）

したがって、複数の「赤黒」アルゴリズムがあります

私があなたの意味を理解したことを願っています。

于 2011-07-19T17:15:38.973 に答える