問題タブ [red-black-tree]

10 個の要素があり、空のツリーから開始する場合、Big-O 記法で赤黒に 10 個の要素を挿入する複雑さは何ですか?

要素を挿入するたびに、要素の適切な場所を検索し、祖先ノードと子ノードの間で一連のローテーションを実行する必要があるため、O(log 10) を超えることはありません。N 個の要素があり、Red Black Tree に N 回挿入すると、O(n log n) になりませんか?

助けてくれてありがとう。

赤黒の木がどのように機能するかを理解しようとしています。写真で最初から2番目への移行を想定しています。これは問題なく取得できます。その後、教育リソースに従って、赤のGノードでローカル修正を行う必要があります. では、2 番目のステップの修正として、赤黒の特性を維持するために G を単に黒に着色するだけですか?

代替テキスト http://img683.imageshack.us/img683/4929/rb1.jpg

ありがとう

次のアクションで実行できるデータ構造を見つける必要があります。

• ビルド (S,k) - O(nlogn)
• 検索(S,k) - O(logn)
• Insert(S,k) - O(logn)
• 削除(S,k) - O(logn)
• Decrease-Upto(s,k,d) - O(logn) - このメソッドは、<=k であるノードごとに d(d>0) を減算する必要があります

明らかに最初の選択は RedBlackTree でした。

ただし、O(Logn) の Decrease-Upto に関する解決策には至りません。k がツリーの最大キーよりも大きい場合はどうなるか - その場合、ツリー全体を更新する必要があります。

誰かがそうでなければ提案できますか? 多分いくつかのヒント？

私は大学でアルゴリズムのコースを取っています。私のプロジェクトの 1 つで、C# で赤黒木を実装したいと考えています (実装自体はプロジェクトではありませんが、私を助けるために選択したものです)。 .

私の赤黒ツリーは文字列キーを保持する必要があり、各ノード用に作成したオブジェクトは次のようになります。

ツリーの印刷、ルートの検索、最小/最大キー (アルファベット順) などの基本的なメソッドを既に追加しました...

ノードの挿入に問題があります (したがって、ツリーを構築します)。赤黒木に詳しい人なら誰でも、片側にノードを追加すると、木のバランスが変わる可能性があることを知っています。これを修正するには、ツリーのバランスを取るために、ツリーのノードを中心に「回転」する必要があります。

RightRotate メソッドと LeftRotate メソッドを疑似コードで作成し、C# で実装しようとしたときに、作成した sRbTreeNode オブジェクトで一連の参照の問題に遭遇しました。

これは、LeftRotate メソッド用に作成した疑似コードです。

最初に試した「ref」キーワードを使用せずに、直接実装するという提案を受けました。これが私がやった方法です：

今、デバッグすると正常に動作することがわかりますが、このメソッドに渡すオブジェクトはメソッドの範囲内でのみ回転されます。このメソッドを終了すると、実際のノードには変更がないように見えます。それが、最初に「ref」キーワードを使用することを考えた理由です。

私は何を間違っていますか？

C# で赤黒木を実装しようとしています。String キー、Color、Left、Right、および Parent プロパティを持つ sRbTreeNode というオブジェクトを既に作成しました。Insert、InsertFixUp、LeftRotate、RightRotate、Delete メソッドの実装に成功しましたが、今は DeleteFixUp メソッドに問題があります。

DeleteFixUp は、削除後に (回転を使用し、ノードの色を変更することによって) ツリーのバランスを再度調整します。

「アルゴリズム入門」という本で見つけた疑似コードからメソッドを実装してみました。

これが私のコードです:

毎回別の場所で「オブジェクト参照がオブジェクトのインスタンスに設定されていません」というエラーが発生し続けます...

これの実装をインターネットで検索したところ、ちょうど私と同じように実装された CodeProject に関する記事が 1 つ見つかりました。私は自分の目で何かを見逃すことを期待して、彼らのコードをコピーしようとしましたが、どちらもうまくいきませんでした...

髪を引きちぎり始める前に、誰か助けてくれませんか!!... ?? :)

私は自分のバージョンの赤黒木を実装してきましたが、そのほとんどはWikipedia（http://en.wikipedia.org/wiki/Red-black_tree）のアルゴリズムに基づいています。ほとんどの部分はかなり簡潔ですが、明確にしておきたい部分が1つあります。

2つの非リーフ（非NULL）の子を持つツリーからノードを消去すると、どちらかの側の子を削除可能なノードに移動し、その子を削除するように指示されます。

それに基づいて、どちらの側から削除するかについて少し混乱しています。サイドをランダムに選択しますか、サイドを交互に選択しますか、それとも将来の削除ごとに同じサイドに固執しますか？

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

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

[編集] たとえば、私のキーが {7, 2, 4, 1, 9, 10, 8} の場合

ここで 7 はルートで黒色を仮定していますが、2 は何色を想定していますか? どうやってそれを決めるのですか？また、他のノードが想定する色をどのように決定するのでしょうか?

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

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

CLR の赤黒間隔ツリーに似た間隔ツリー アルゴリズムを探していますが、既定で間隔のマージをサポートしているため、間隔が重複することはありません。

つまり、2 つの間隔 [2,3] と [5,6] を含むツリーがあり、間隔 [4,4] を追加すると、結果は 1 つの間隔 [2,6] のみを含むツリーになります。

ありがとう

更新: 私が検討しているユース ケースは、推移閉包の計算です。間隔セットは、非常にコンパクトであることがわかっているため、後続セットを格納するために使用されます。しかし、間隔セットをリンクされたリストとして表すと、状況によっては間隔セットが非常に大きくなり、挿入ポイントを見つけるのに必要な時間がかかることがわかりました。したがって、インターバルツリーに興味があります。また、1 つのツリーを別のツリーとマージする (つまり、セット OR 操作) ことが非常に多い場合があります。両方のツリーが大きい場合は、各間隔の挿入を繰り返すよりも、両方のツリーの順序どおりのウォークを使用して新しいツリーを作成する方がよい場合があります。

のコードを使用して、task_struct ごとに Linux に赤/黒のツリーを実装しようとしていますlinux/rbtree.h。モジュールなどのカーネル内のスタンドアロン スペースに適切に挿入された赤/黒のツリーを取得できますが、またはでrb_root宣言された同じコードを機能させようとすると、挿入を試行するたびにエラーが発生します。task_structtask_struct->files_structSEGFAULT

ここにいくつかのコードがあります：

task_structrb_rootで、ツリーの構造体を作成します (ポインターではありません)。init_task.h、マクロではINIT_TASK(tsk)、これを に等しく設定しRB_ROOTます。挿入を行うには、次のコードを使用します。

ここで問題が発生します。

私の挿入コマンドは、カーネルのすべての RBTree ドキュメントに記載されている標準の挿入です。

足りないものはありますか？

何らかの理由で、ツリーのルートを外に作成した場合、これはうまく機能しtask_structますか？モジュール内に作成するrb_rootと、この挿入は正常に機能します。しかし、実際のツリー ルートをtask_structまたは に配置するtask_struct->files_structと、SEGFAULT. これらの構造体にルート ノードを追加できませんか?

どんなヒントでも大歓迎です。私は考えられるほとんどすべてを試しました。

編集：

SEGFAULT印刷しようとすると、次の行とツリーにアクセスする行にaが表示されます。この行で、私がポインターをどのように処理しているかを理解する必要があります。rb_entryおよびrb_firstカーネルですでに使用可能なメソッドです。currentはタスク構造体（現在の作業プロセス）へのポインターであり、ツリーはタスク構造体のメンバーであるルートノード（ポインターではない）です（追加しました）。rb_firstポインタを渡す必要があります*rb_root。私はこれを間違っています。

rb ツリーに問題があります。ウィキペディアによると、rb-tree は次に従う必要があります。

1. ノードは赤または黒のいずれかです。
2. 根元は黒。(この規則はいくつかの定義で使用され、他の定義では使用されません。ルートは常に赤から黒に変更できますが、必ずしもその逆であるとは限らないため、この規則は分析にほとんど影響しません。)
3. 葉はすべて黒い。
4. すべての赤のノードの子は両方とも黒です。
5. 特定のノードからその子孫の葉のいずれかへのすべての単純なパスには、同じ数の黒いノードが含まれます。

ご存知のように、rb-tree はバランスを取る必要があり、高さは O(log(n)) です。しかし、増加する一連の数字 (1、2、3、4、5...) を挿入すると、理論的には、リストのように見え、すべての O(n) の高さを持つツリーが得られます。これは、上記の rb ツリーのプロパティと矛盾しません。それで、どこが間違っていますか??

ありがとう。