問題タブ [red-black-tree]

メガバイトからテラバイトまでの範囲のデータに対して高速な検索、挿入、および削除操作を実行する必要があるプロジェクトがあります。私は最近のデータ構造を研究し、分析していました。具体的には、3 つのケースを紹介し、それについて質問したいと思います。

1. データは、メモリが一度に処理できる量 (サンプル範囲は 10 ～ 15 テラバイト) をはるかに超えています。この場合、データ構造をディスクに保存します。

2. データはシステムのメモリに比べて比較的少ないため、速度のためにメモリ自体に保存および操作できます。

3. データは空きメモリを超えており、ページング ファイル内の可能な連続したデータ チャンクのサイズよりも小さいと想定します。したがって、データ構造をディスク上のファイルに保存し、ファイルのメモリ マッピングを行います。

私が導き出した結論は次のとおりです。

ケース 1 の場合、ディスクのローテーションによって生じる遅延を節約できるため、アクセスを高速化するために B ツリーを使用する必要があります。

ケース 2 では、データがメモリ上にあり、ないため、アクセスを高速化するために Red Black Tree を使用する必要があります。最悪の場合、スキャンする必要がある要素の数は、B ツリーを使用する場合に必要な要素よりも少なくなります。

ケース 3 については、これには疑問があります。ページ ファイルはディスク上にあり、ネイティブ OS I/O を使用してファイルを操作します。したがって、B ツリーの方が適切なオプションでしょうか、それともレッド ブラック ツリーでしょうか?

上記の 3 つの結論のどこが正しく、どこが間違っているか、また 3 つの別々のケースでどのようにパフォーマンスを改善できるかを知りたいです。

私は C++ 言語を使用しています。赤い黒いツリーと B ツリーがあり、どちらもゼロから設計したものです。ファイル マッピングに Boost ライブラリを使用しています。

更新 1:: stackoverflow でこの投稿を読んでいました。本当に良い洞察を得たので、私がケースで行ったタイプの比較は間違っているかもしれないと感じています. 最も投票数の多い回答にリンクが投稿されましたhttp://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

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

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

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

アップデート

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

私は2つのローカルディレクトリ間の一貫性を維持することを含むアプリケーションに取り組んでいます。具体的には、ディレクトリの1つにあるすべてのファイルが特定の方法で変更されることを除いて、ディレクトリは同一である必要があります（この部分は私の質問にとって重要ではありません）。

実行中、アプリケーションは各パスで発生する変更をリッスンする2つのプロセスを実行し、必要に応じてそれらを同期に戻すための関連操作を実行します。

私の具体的な質問に関して：私は、アプリケーションを開始するときのトリッキーな状況についてのアドバイスを探しています。この時点で、各プロセスは、処理している両方のパスの下にあるすべてのファイル/フォルダーをチェックして、アプリケーションの実行中に何らかの変更があったかどうかを確認する必要があります。（アプリケーションがシャットダウン中に発生したことをOSから通知できないため、すべてのファイル/フォルダーを直接チェックする必要があると想定します。）

各プロセスは、指定されたパスの下にあるすべてのファイル/フォルダーの永続的なデータ構造にアクセス（および維持）します。私は、各ファイルとフォルダーのデータ構造内に次のものを保持する必要があると考えていました。

• ファイル/フォルダ名;
• ファイルハッシュ（CRC32）;
• ファイル/フォルダーの最後のmodデータ。と
• ファイル/フォルダのサイズ。

これらの情報は明らかにファイル/フォルダへの変更をチェックするのに役立ちますが、それらを保存するための最良の方法は何ですか？

アプリケーションの開始状況にアプローチするための賢明な方法の1つは、各プロセスが指定されたパスの下にあるすべてのファイル/フォルダーを再帰的にスキャンし、スキャンされた各ファイルのメタデータをそのデータ構造に格納されているメタデータと比較することです。 。次に、プロセスはデータ構造を反復処理して、パスから削除されたものを探す必要があります。このプロセス中に発生する可能性のあるいくつかのケースは次のとおりです。

• ファイルが変更されました（ファイル名はデータ構造にありますが、ハッシュは異なります）。
• 追加されたファイル（データ構造に同一のファイル名またはハッシュが見つかりません）;
• ファイルの名前が変更されました（同じハッシュを持つファイルはデータ構造に存在しますが、同じファイル名ではありません）;
• フォルダが追加されました（データ構造にフォルダ名がありません）;
• フォルダーが削除されました（データ構造内のフォルダー名ですが、パスの下にはありません）;
• フォルダの名前が変更されました（トリッキーなもの）。

では、このタスクに使用するのに最適なデータ構造は何ですか？私の頭の中で、私はある種のソートされた連想配列、たとえば赤黒木を格納fileしてfolderオブジェクトを格納することを考えています。各fileオブジェクトにはname、hashとmod-date属性が含まれ、各folderオブジェクトにはnameとchildren属性が含まれ、childrenその下にあるすべてのものを含む別の連想配列が格納されます。任意のファイルへのパスを指定します。たとえば、/foo/bar/file.txtルート（）から開始し、の親オブジェクトに到達するまでfooチェックします。barfile.txt

私が考えることができるもう1つの方法は、すべてをフラットに格納することです。たとえば、各キーが各ファイル/フォルダーへのフルパスであり、値がfile/folderオブジェクトである赤黒木が1つあります。これはおそらく検索の方が速いでしょうが、とにかくすべての値を反復処理せずに名前が変更されたファイル/フォルダーを検出することはできません。これはコストがかかるように聞こえます。最初のアプローチでは、名前変更の識別には、データ構造のすべてではなく一部のチェックのみが含まれる場合があります。

申し訳ありませんが、上記のアイデアはひどくよく考えられていません。この分野の最先端は何ですか、そしてこれらのタイプの問題へのよく踏まれたアプローチはありますか？

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

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

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

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

「アルゴリズム入門、第2版」から：C++での削除アルゴリズムの実装は次のようになります。

問題は、1、2、3、4、5、6、7、8の順序でツリーを作成すると、ツリーが次のようになることです。

このツリーからルートを削除すると、次のようになります。

このコードは明らかに機能しません。この質問の冒頭で述べた本から1行ずつ実装されていることに注意してください。

誰かが私を助けて、どうやってそれを修正するのか説明してもらえますか？

自己平衡二分木に関するいくつかのQ＆Aを読みましたが、それらすべてに精通しているわけではありません。

私が知った最初のものはAVLで、2番目は赤黒木です。

私がよく理解していないことがあります。いくつかの本や記事によると、AVLは赤黒木よりも少し速く検索を実行できます。これは理解できます。

1. では、AVLに対する赤黒木のエッジは何ですか？

2. AVLでは、おそらく挿入のたびにバランスをチェックする必要がありますが、赤黒木ではそのようなことを頻繁に行う必要はありませんよね？

PS：私はSOで似たようなものを検索しましたが、満足のいく答えは得られませんでした。何人かの友人が私に自己平衡木の詳細な比較を教えてくれることを願っています。

授業で赤黒木のコードを教えてもらいました。ノードの作成に使用される構造体に親ポインターがありません。プロジェクトのほとんどが機能していますが、O(lg n) 時間でランクを計算する方法がわかりません。ランクとは、inorder-traversal を実行し、キーをインデックス 1 から始まる配列に保存する場合、指定されたキーが保存されるインデックスを意味します。これを行うと O(n) 時間になりますが、これは許可されていません。

CLRS を読んで、Augmenting Data Structures の章に、キーを指定してランクを返すコードがあります。これはまさに私が必要としているものですが、問題はコードが親ポインターを使用していることです。赤黒木の例では親ポインターを使用したことがなく、このコードには親ポインターが含まれていないため、ランクを機能させるためだけに指定されたコード全体を変更する必要はないと思います。親ポインターを使用せずにそれを行う方法があると信じています。

ノード構造体に存在する (フィールド?) は、キー (int)、左の子へのポインター、右の子へのポインター、サブツリー サイズ (int)、および色 (int) です。

すべてのコードは C で行われます。私が探しているのは、これが可能かどうか、およびソース コードの有無にかかわらずこれをどのように達成できるかです (適切な説明があれば完璧です)。

私は次のデータ構造の知識を持っており、実際のアプリケーションでのそれらの使用例を探しています。

• 二分探索木
• 赤黒木
• 区間木（拡張RBT）
• ハッシュテーブル