問題タブ [red-black-tree]

私は c++ で実装された Red Black ツリーを持っています。STL マップの機能をサポートします。ツリー ノードには、マップされたキーと値が含まれます。このための反復子クラスを書きたいのですが、その方法に行き詰まっています。Tree クラスの内部クラスにする必要がありますか? 誰かがそれを書く方法といくつかのリソースに関するガイドラインを教えてもらえますか??

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

ソートされたオブジェクトのセットが必要で、現在TreeSet. 私の問題はcompareTo、オブジェクトの がしばしば を返すことです0。つまり、これら 2 つのオブジェクトの順序は変更されないままにしておく必要があります。TreeMap(TreeSetデフォルトで使用) はそれらを同じオブジェクトと見なしますが、これは正しくありません。

どのような代替手段をTreeMap使用できますか?

ユースケース: 表示可能なオブジェクトのセットがあります。正しい順序でレンダリングされるように、Y 座標で並べ替えたいと思います。もちろん、2 つのオブジェクトの Y 座標が同じ場合もあります。

SetOCaml標準ライブラリには、非常に効率的な分割統治アルゴリズムを使用して2つのセットのを計算する素晴らしい実装がunionあります。あるセットからサブツリー全体（単一の要素だけでなく）を取得し、それらを別のセットに挿入して、必要に応じてバランスを取り直すと思います。

これには、OCamlが使用するAVLツリーに保持されている高さ情報が必要なのか、それとも赤黒木でも可能かどうか疑問に思っています。たとえば、最初のツリーの最後に要素を追加する2番目のツリーを単純に反復するよりも、赤黒木のペアをより効率的に連結することは可能ですか？

赤黒木の回転方法を覚える簡単な方法はありますか?

ハッシュ テーブルを使用するよりも、自己均衡ツリー手法を使用してアイテムを保存する方が優先される理由を知りたいです。

ハッシュ テーブルは挿入順序を維持できないことがわかりましたが、リンク リストを常に使用して、挿入順序シーケンスを格納できます。

少数の値の場合、ハッシュ関数のコストが追加されることがわかりますが、ルックアップを高速化するために、ハッシュ関数をキーと一緒にいつでも保存できます。

ハッシュ テーブルは、赤黒ツリーの単純な実装よりも実装が難しいことは理解していますが、実際の実装では、問題を解決するために余計な努力をしたいとは思わないでしょうか?

ハッシュ テーブルでは衝突が発生するのは普通のことですが、ハッシュ テーブル自体にキーを保存できるようにするダブル ハッシュなどのオープン アドレッシング技術では、問題は有利にならないという効果にまで軽減されていません。そのような実装のための赤い黒い木に向かって？

実際のアプリケーション（ファイルシステムなど）で赤黒木を非常に実行可能なデータ構造にするハッシュテーブルの欠点を厳密に見逃しているかどうか、私は興味があります。

a への挿入の最悪の場合の実行時間は でred-black treeあり、ツリーでO(lg n)a を実行する場合in-order walk、基本的に各ノードにアクセスするため、ソートされたコレクションを出力するための最悪の場合の合計実行時間は O(n lg n) になります。

私は興味があります.なぜred-black treesソートに好まれないのですかquick sort（その平均ケースの実行時間はO(n lg n).

そのred-black trees場でソートしないためかもしれませんが、よくわからないので、誰かが助けてくれるかもしれません。

私は自分で赤黒木を書くことに取り組んでいます。しかし、ルートを回転させる回転をテストすると、参照が多少失われます。

ツリー構造：

回転ロジックは次のように述べています。「X（つまり40）を上げる方向に、45（ルート）を上にして回転します。」

つまり、これは右回転を意味し、結果は次のようになります。

ノード45が祖父母で、7が親で、41が現在であると仮定します。（順序が意味をなさないことはわかっていますが、無視してください。これは、すでに1回回転したためです）

コード：

しかし、どういうわけかこのコードは機能しません。私がテストしたとき：

したがって、結果は実際には次のようになります。

誰かが私のローテーションコードの何が問題になっているのかヒントを教えてもらえますか？

赤黒木では、回転するとき、特定のノードの親が誰であるかを知る必要があります。ただし、ノードは右または左の子への参照しかありません。

ノードインスタンス変数に「親」を与えることを考えていましたが、この理由からそうする価値はないと思います。また、回転ごとに親参照を変更するのは複雑すぎるでしょう。

したがって、私の解決策は、検索を使用して親を見つける findParent() メソッドを作成することです。ノードの親を見つける他の方法があるかどうか疑問に思っていますか?

私の解決策：

サンプルツリー:

ノード 25 の親を見つけたい場合は、次のようなものを渡します。

node50 を返します。

TreeSet のいくつかの操作の複雑さに関するいくつかのことを解決しようとしています。javadoc には次のように書かれています。

「この実装は、基本的な操作 (追加、削除、および含む) の保証された log(n) 時間コストを提供します。」

ここまでは順調ですね。私の質問は、addAll()、removeAll() などで何が起こるかです。ここで Set の javadoc は次のように述べています。

「指定されたコレクションもセットである場合、addAll 操作はこのセットを効果的に変更し、その値が 2 つのセットの結合になるようにします。」

操作の論理的な結果を説明しているだけですか、それとも複雑さについてのヒントを提供していますか? つまり、2 つのセットがたとえば赤黒の木で表されている場合、一方の要素を他方の要素に「追加」するよりも、どうにかして木を結合する方がよいでしょう。

いずれにせよ、2 つの TreeSet を O(logn) の複雑さで 1 つに結合する方法はありますか?

前もって感謝します。:-)

みんな私はレッドブラックツリーの削除アルゴリズムを実装しようとしていますが、このアルゴリズムの3行目を理解するのに問題があります(本「アルゴリズムの紹介」第2版から):

1 if left[z] = nil[T] or right[z] = nil[T]
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5 then x ← left[y]
6 そうでなければ x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9 then root[T] ← x
10 else if y = left[p [y]]
11 then left[p[y]] ← x
12 else right[p[y]] ← x
13 if y 3≠z
14 then key[z] ← key[y]
15 yの衛星データをzにコピー
16 color[y] = BLACK の場合
17 then RB-DELETE-FIXUP(T, x)
18 return y

まず第一に、この本のどこにも TREE-SUCCESSOR がどのように見えるかを説明していません (そのためのアルゴリズムはありません) 。 ,14,15,4 を削除してから 7 を削除しようとすると、先行者が見つかりますが、11 を削除しようとすると後続者が見つかります。そして、それは私が理解できないものです。なぜ時には前任者が必要なのか、時には後継者が必要なのか? この決定を下す際に考慮される基準は何ですか? ノードの色？
ありがとうございました。

PS 13 行目に書かれていることもよくわかりません。y に 3 つの色 (黒でも赤でもない) があるかどうかということですか?