問題タブ [red-black-tree]

フェイルファストではない反復子を提供する赤黒木とリンク リストの実装を備えたライブラリを探しています。STL を使用して C++ で行っているのと同じ機能を持ちたいのですが、それは次のとおりです。

• ツリー/リストへの挿入はイテレータを無効にしません
• 削除は、削除される要素を指すイテレータのみを無効にします
• イテレータの「位置」を何らかの方法で保存し、それが指している値を参照することが可能です

この実装は、その一部を使用しながらリスト/ツリーを変更する機能を提供するため、優れています。ここではいくつかの例を示します。

• リンクされたリスト/赤黒ツリーの隣接要素をO(1)に格納された値に取得する
• 一括挿入/削除 (位置の増分ごとに 1 つの削除などの制約なし)
• イテレータの位置を介して O(1) でリンクされたリストを分割する
• イテレータの位置を保存している場合のより効率的な削除 (たとえば、イテレータをリンクされたリスト内の位置に保持することにより、削除は O(N) ではなく O(1) になります)

また、そのライブラリ/ソース コード/実装に Apache/GPL に適したライセンスがあり、かなり拡張可能であることも望んでいます (上の例のような操作を実装するために独自の変更を加えることができます)。

そのようなライブラリが存在しない場合、これらの 2 つのデータ構造を自分で実装するのに役立つ他のライブラリはありますか?

新しいホーム プロジェクトの作業を開始しました。特定のファイル名にパスを付けてインデックスを作成する必要があります。プログラムは、ファイルの内容を処理する必要なく、ローカル ハードディスク上のファイルにインデックスを付けます (したがって、単純な実装であると想定/期待しています)。最初に、ユーザーはファイル拡張子のリストを挿入してインデックスを作成します (セットアップ時に)。次に、プログラムが実行され、ユーザーが入力した特定のファイルのパスを保持するデータ構造が作成されます。

データ構造からデータを取得すると、次のようになります。

HDD 上のファイルのパス = 関数 (ユーザーが入力したファイル名)

私はそれについてかなり長い間考え、ここにデータ構造のデザインを書きました。これが私の提案です (デザインの図):

1. 拡張子をセルにマッピングするためのハッシュ関数を持つ配列を使用します (各セルは
   拡張子ファイルの最初の文字を表します)。

2. 各セル内には、同じ文字で始まる拡張子のリストがあります。

3. リスト内の各ノードには、ファイル名を検索するための赤黒のツリーがあり、ファイル名が見つかった後、プログラムはツリー
   ノードに格納されているファイルのパスを取得します。

ところで、私は通常、c (低レベル) または c++ でプログラミングします。

ここでは一般的な背景が必要ですが、オンラインで見つけることができません..

私の主な疑問は、赤黒ツリーでマルチセット構造を実装したい場合、マルチセットのすべての要素 (すべての繰り返される要素も..) RB ツリーに配置する必要があるか、または一意の要素を保存する方法があるかどうかです。そしてそれらの多様性？

これはすべて、他の構造ではなく、1 つの赤黒木でのみ行う必要があります。（ご想像のとおり、これは宿題です。）

ダミーノード（つまり、リーフノードが実際にはnullポインターである）を使用せずに赤黒木で要素の削除を実装する方法のガイドを探しています。私がグーグル/ウィキペディアと標準的な文献（sedgewickとcormenなど）で見つけたすべての実装は、ダミーのNILノードを使用しています。これは避けたいと思います。

自己平衡ツリーを使用して実装された連想配列で衝突はどのように処理されますか? 2 つのオブジェクトが同じハッシュを持つ場合、それらはツリー ノードに接続されたリンク リストに格納されますか、それとも 2 つのノードが作成されますか? 前者の場合はO(log n)どうですか？後者の場合、二分探索木はどのように同じキー（ハッシュ）を処理できますか？

以前に作成した同様のAVLツリーと比較できるように、挿入、検索、および順序どおりのトラバーサルメソッドのみを実装する赤黒木を作成しようとしています。コーメンのテキスト「アルゴリズムの概要」にあるすべてのアルゴリズムを使用しましたが、何らかの理由で正しく機能しないようです。

たとえば、a、b、cの順に挿入して順番に走査しようとすると、cが失われます。私はテキストのアルゴリズムを約10回調べて、すべてが正しく、間違いを見つけられないことを確認しました。

insertFix()私がメソッドを正しく実行しているかどうか、およびローテーションを誰かに教えてもらえますか？

以下は、ノードをどのように設定したかを示すためのヘッダーファイルです。

そしてinsertFix()、これが私のメソッドです。これは、通常のバイナリ検索ツリーにある通常の挿入の後に実行されます。

以下は私の2つの回転方法です。1つは右回転（RR）で、もう1つは左回転（LR）です。

私はこれが見過ごされるべき多くのコードであることを知っています、しかし私は自分が間違っていることを見つけようとしている私の知恵の終わりにいます。回転のどこかでポインタをめちゃくちゃにしているような気がしますが、どこにあるのかわかりません。どんな助けでも本当にありがたいです！

赤黒の木のノードは、赤と黒の子を 1 つずつ持つことができますか?

私は次のツリーを持っています。ここでは色だけを指定しました。リーフ ノードは無視されます。

私の宿題からの質問の 1 つは、の正確な下限を見つけることでした。

rb ツリーで。境界は漸近的であってはなりません。助言がありますか？

どうぞよろしくお願いいたします。

私は現在、アプリケーションのいくつかの最適化を実行するために赤黒木データ構造を実装しています。

私のアプリケーションでは、特定の時点で、特定の値以下のすべての要素（要素は整数であると見なすことができます）をツリーから削除する必要があります。

要素を1つずつ削除することもできますが、もっと速くしたいのですが。したがって、私の質問は、赤黒木のサブツリー全体を削除した場合、高さと色の不変量を回復するためにツリーを修正するにはどうすればよいですか？