問題タブ [red-black-tree]

私の STL (g++ 4.xx に付属) は赤黒木を使用して、マップなどのコンテナーを実装することを理解しています。STL の内部赤黒ツリーを直接使用することは可能ですか。もしそうなら、どのように？そうでない場合は、なぜ STL が赤黒ツリーを公開しないのですか?

驚いたことに、私はグーグルを使って答えを見つけることができません。

編集:挿入時の余分なアロケーターコンストラクター呼び出しの解決策として、赤黒ツリーを使用して調査しています。この質問を参照してください。私の STL では、マップの実装に赤黒木を使用しています。

特に学習のために、ネット上で赤黒木の実装を見つけるのは簡単ではありません。

シンプルな赤黒ツリーの実装 (C# 推奨)はどこにありますか?

Nそれぞれのエンドポイントによって決定される、円内のコードを考えてみましょう。O(nlogn)円の中で交差する弦のペアの数を求める解を説明してください。

仮定: エンドポイントを共有する 2 つのコードはありません。

私の本によると、AVL ツリーで偶数の高さのノードから奇数の高さのノードに移動する赤いリンクに色を付けると、(完全にバランスのとれた) 2-3-4 ツリーが得られます。ここで、赤いリンクは必ずしも左寄りではありません。しかし、正確にはわかりません。いくつかの例で試してみると、行き詰まります。誰かが私のためにそれを説明してもらえますか?

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

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

このような赤黒木は次のようになります。

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

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

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

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

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

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

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

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

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

このクラスが赤黒木を使用していることは知っていますが、それは O(log(n)) で最小の要素を取得することを意味するのでしょうか、それとも O(1) か何か他のものでしょうか?

ありがとう！

ここで非常に簡単な質問があります。赤黒木は並べ替えられた順序である必要がありますか？ウィキペディアページ（http://en.wikipedia.org/wiki/Red–black_tree）の右側にある小さなボックスには、検索時間はO（log（n））と書かれているので、これを尋ねます。ただし、これは、ツリーがソートされている場合にのみ当てはまります。一方、プロパティは

どうやらあなたはどちらかを行うことができますが、前者がより一般的です。

なぜ後者を選ぶのですか、そしてそれはどのように機能しますか？

私はこれを読みました：http ：//www.drdobbs.com/cpp/stls-red-black-trees/184410531 ; それは彼らがそれをしたと私に思わせました。それは言う：

insert_alwaysは、同じキー値の複数のインスタンスが許可されているかどうかをrb_treeに通知するステータス変数です。この変数はコンストラクターによって設定され、STLによって使用されて、セットとマルチセット、およびマップとマルチマップを区別します。setとmapは、特定のキーを1回だけ出現させることができますが、multisetとmultimapは、複数回出現させることができます。

今は必ずしもそうとは限らないと思いますが。彼らはまだコンテナを使用している可能性があります。

同じキーを持つすべてのノードを右側または左側に格納する必要があるため、同じキーを持つすべてのノードが連続している必要があると思います。したがって、等しいノードを右側に格納し、1000個の1と1個の2を挿入すると、基本的にリンクリストが作成され、赤黒木のプロパティが台無しになります。

それが悪い考えだということで私がそれについて多くを見つけることができない理由はありますか？

QMapがrb-treeではなくスキップリストのデータ構造で実現したのはなぜですか？並行性データ構造体とスキップリストの利点については、rb-tree、長所、短所よりも非常に興味深いSOスレッドがあります。それは確かに有用なリンクを備えた非常に興味深いダイアログですが、QMapはスレッドセーフではなく、箱から出してアクセスを同期するためのミューテックスロックを行いません。ラッパーまたはサブクラス化が必要です。

私にとっては、rb-treeの代わりに「手作り」のスキップリストを書くのは簡単ではないので、これも明らかではありません。

スレッドセーフではないQtコンテナのコンテキストでkill機能はありますか？

事前にTnx。

背景：約10億のキーと値のペアを挿入します。（一意の64ビット整数）キーの（32ビット整数）値を同時に検索できるメモリ内インデックスが必要です。更新、削除、トラバースはありません。キーは一般的に時間とともに徐々に増加しています。

これを処理するのに最も適切なインデックス構造は何ですか？

私が考えることができる要件は次のとおりです。

• キーが増えるため、効率的なリバランスが必要です
• RAMに収まるようにメモリを効率的に使用する必要があります。できれば28GB未満です。
• 非常に効率的なルックアップが必要です