1

一意の値 (セットなど) を保持するだけでなく、それらを並べ替え (プライオリティ キューなど) し、バイナリ検索のランダム アクセス (配列など) を可能にするデータ構造が必要です。これらのニーズに適合するのはどのタイプのデータ構造ですか? 選別しなくても生きていける（最後はいつでも自分で選別できる）

4

2 に答える 2

4

これは、バランスのとれた二分木のように聞こえますが、挿入操作の一意性に制限があり、O でランク (「インデックス」) を指定して要素を取得するためのOS-SELECT操作を実装しています (アルゴリズムの概要、第 3 版の第 14 章を参照)。 (lg n).

提案されたデータ構造と拡張された操作により、次のことが可能になります。

  • 一意の値を保持し、O(lg n) で挿入操作を実行します
  • O(lg n) 検索操作を使用して、要素を並べ替えたままにします
  • O(lg n) のランクを指定して要素にアクセスする
于 2012-06-17T19:10:48.417 に答える
0

TreeSetまたはTreeMapはどうですか？

  • 一意の値 - どちらも一意の値のみを保存します
  • 並べ替え - 要素の自然な順序を使用するか、要素に提供されたカスタム Comparator を使用してエントリを並べ替える
  • ランダム アクセス - どちらもランダム (O(1)) アクセスを提供します。
于 2012-06-18T00:35:26.497 に答える