13

有効な二分探索木であり、これらの規則のいずれにも違反しない赤黒木があるとします。

  • ノードは赤または黒のいずれかです。
  • 根元は黒。
  • すべての葉 (NIL) は黒です。
  • すべての赤のノードの子は両方とも黒です。
  • 特定のノードからその子孫の葉のいずれかへのすべての単純なパスには、同じ数の黒いノードが含まれます。

このような赤黒木は次のようになります。 ここに画像の説明を入力

これらの制限を満たす可能性のあるすべてのツリーには、赤黒ツリーが生成されるように一連の挿入と削除がありますか?

赤黒木についてのブログ記事を書くことを考えており、いくつかの例を挙げたいので、この質問をしています。

反例をテストする場合: これは、画像を生成する関数が実装された Python での赤黒ツリーの実装です。

質問を明確にするために：私たちはゲームを作ります。

  • すべての制限を満たす赤黒の木を描きます。
  • 挿入と削除のシーケンスを見つける必要があるため、最終的に私の赤黒の木になります。

勝てないように赤黒の木を描いてもいいですか？

色は大事！形や色が違う木は、同じ赤黒木ではありません。

少なくとも、これら 2 つの赤黒木を生成する方法を知っている必要があります。 ここに画像の説明を入力 ここに画像の説明を入力

これは、機能するかどうかのチェックにすぎないことに注意してください。この 2 本の赤黒木を入手する方法しか知らないと、この質問には答えられません。

4

6 に答える 6

5

ノードを幅優先 (レベル順) トラバーサルで挿入すると、赤黒木が生成されると思います。

http://en.wikipedia.org/wiki/Tree_traversal#Queue-based_level_order_traversal

それらをレベル順に挿入するため、元の木よりもバランスの取れていない木を持つことはできません。削除は必要なく、挿入時にローテーションも必要ありません。あなたの例では、次の順序で挿入する必要があります。

13,8,17,1,11,15,25,6,22,27

編集:これにより、適切な値と形状のバイナリ検索ツリーが生成されますが、適切な色が生成されない場合があります...挿入機能の実装に依存します。その理由は、ツリーに複数のノードがあり、満杯で、すべての葉が同じ深さである場合、赤黒ツリーの定義により、ノードの色のバリエーションが許容されるためです。ウィキペディアの定義に従って、これは「完全な」バイナリ ツリーです。

http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

ツリーに値 {1,2,3} を持つ 3 つのノードがあるとします。"2" はルートであり、定義により黒です。ノード {1,3} は、赤黒の規則に違反することなく、両方とも黒または両方とも赤である可能性があります。したがって、赤黒挿入の完全に有効な実装は、ツリーが「完全」であることを検出し、すべてのノードを黒く着色することができます。このような実装では、たとえば、各レベルで黒と赤を交互に使用するツリーを構築できなくなります。

編集 2: 両方の赤黒ツリーが可能な入力 (3 つのノードはすべて黒、ノード 1 と 3 は赤) であることを考えると、削除が必要かどうかという問題が解決されます。解決策がある場合は、削除が必要です。私が今考えている問題は、赤黒ツリーの挿入/削除を実装する方法が 1 つしかないかどうかということです。複数のツリーがあり、それらが異なるツリーを生成する場合、ゲームのプレイヤーは、特定の赤黒ツリーを構築するために挿入と削除の順序を指定するために、実装を理解する必要があります。赤黒木を実装する方法が 1 つしかないのか、それとも複数あるのかという質問に答えるには、赤黒木の実装について十分に知りません。

于 2012-08-04T20:37:17.200 に答える
4

ここで求めているのは、操作のたびにツリーのバランスを取り直せば、一連の挿入と削除によって、任意の正当な赤黒木を構築できるかどうかの正式な証明だと思います。私はそのような証明を試みるつもりはありませんが、あなたがそのような証明をどのように構築することができるかについての考えを持っていると思います。

私は、単一ノードの周りのすべての合法的な順列を含むすべての可能なサブツリーを徹底的にカバーし、それが構築できることを証明します。それで：

  • 黒ノード
    • 親なし
      • 子をnullのままにしました
        • 右の子null
        • 右の子はnullではありません
      • 左の子はnullではありません
        • 右の子null
        • 右の子はnullではありません
    • 左の子です
      • 同上
    • 正しい子です
      • 同上
  • 赤いノード（親を持つことはできません）
    • 左の子です
      • 同上
    • 正しい子です
      • 同上

次に、任意のツリーが上記のケースの順列であることを示す帰納的ステップを作成する必要があります。そのように言うと、かなり簡単に思えますが、コメントで述べたように、私は錆びすぎて実際の証拠に取り組むことができません。

于 2012-08-04T19:32:56.233 に答える
3

そのような問題を扱う数学の分野はグラフ理論だと思います。赤黒やその他のバランスの取れた木の特性を検証するグラフ理論の論文を調べていると、次の論文にたどり着きました: http://www.math .unipd.it/~baldan/Papers/Soft-copy-pdf/cosmicah05.pdfおよびhttp://www.math.unipd.it/~baldan/Papers/Soft-copy-pdf/cosmicah05.pdfおよびこのペーパーhttp ://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.1161&rep=rep1&type=pdf、抽象プロパティに関するクエリに回答できるはずです。または、少なくとも、さらに優れたリソースにつながる方法で質問を表現するのに役立ちます.

于 2012-07-31T05:49:04.220 に答える
2

ツリーが次の規則に従う場合:

  • ノードは赤または黒のいずれかです。
  • 根元は黒。
  • すべての葉 (NIL) は黒です。
  • すべての赤のノードの子は両方とも黒です。
  • 特定のノードからその子孫の葉のいずれかへのすべての単純なパスには、同じ数の黒いノードが含まれます。

それはバランスの取れた二分木となり、赤黒木と呼ぶことができます。

赤黒木の挿入と削除には、特別な条件とルールがあります。あなたの例のようなツリーがRBツリーの挿入と削除のアルゴリズムに従う場合、それは常にRBツリーになります。挿入と削除の間、バランスの取れていない二分木は、ノードの色を変更したり、ノードやブランチを回転させたりすることで、常にバランスのとれたツリーに復元されます。

于 2012-08-04T06:38:07.140 に答える
-1

レッド ブラック ツリーは、柔軟なレッド キャッシュと不変のブラック サポートに分解されます。黒の高さを不変に保つには、高さを調整できるように赤のキャッシュを上部に移動する必要があります。大まかに言えば、実際のノードを移動せずに赤の容量を簡単に移動できます。赤のキャパシティーは、グローバルな赤のウォーターフォールを生成するブラック ツリー トップに常にスワップ アウトする必要があります。

赤い容量が下に移動し、黒い枝が上に移動します。

于 2021-10-13T14:48:25.817 に答える