4

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

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

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

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

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

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

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

4

2 に答える 2

2

複数のノードとしてのストアの欠点：

  1. ツリーサイズが拡大し、検索が遅くなります。

  2. キーKのすべての値を取得する場合は、M * log（N）時間が必要です。ここで、Nは合計ノード数、MはキーKの値の数です。ただし、追加のコードを導入する場合を除きます（データ構造が複雑になります）。これらの値のリンクリストを実装します。（コレクションを保存する場合、時間計算量はlog（N）のみで済み、実装は簡単です）

  3. 削除するのによりコストがかかります。マルチノード方式では、削除するたびにノードを削除する必要がありますが、collection-storageでは、キーKの最後の値が削除されたときにのみノードKを削除する必要があります。

マルチノード方式の良い面は考えられません。

于 2012-09-28T07:37:37.733 に答える
2

定義上、二分探索木に重複を含めることはできません。それらを使用してソートされたリストを作成すると、重複を破棄すると誤った結果が生成されます。重複する問題が発生したとき、PHPでの赤黒木の実装に取り​​組んでいます。このツリーを使用して、並べ替えと検索を行います。ノードのデータ型にオカレンス値を追加することを検討しています。重複が発生した場合は、発生をインクリメントするだけです。ツリーを歩いて出力を生成するときは、発生回数だけ値を繰り返します。私はまだ有効なBSTを持っていて、最適な検索時間を維持する重複値のチェーン全体を持つことを避けていると思います。

于 2014-08-13T17:11:59.333 に答える