2つのAVLツリーの代替

私は現在、時間と空間の複雑さから2つの異なる方法でソートする必要があるデータを持っています。日付とID番号でソートされた2つのツリーを維持する方法はありますか？データの順番でリストを返すことができるようにする必要があります。個々のユーザーはIDで検索する必要があります。トラバースしたり、悪化したりすることなく、配列の戻り値をソートして並べ替えます。2つのAVLツリーの代替

洞察または助けが大変ありがとうございます。

出典

2017-02-28 Harrison W.

これは1つのツリーで行うことができますが、その日だけO（logN）のパフォーマンスが得られます。 IDの直接検索は、順序が決定されないので、とにかくO（N）（即ち、正確な一致を見つけるためにツリー全体を走査する）となる。

あなたのIDがあなたが必要とする日付に基づいていれば（つまり、その日付に基づいてIDを生成することができます）、O（N）時間の複雑さをO（logN + M）ここで、M - は特定の日付のIDのサブセットです。

応答時間とメモリの要件によっては、ツリーを1つだけ保持することも、IDのHashMapとペアリングすることもできます。

出典

2017-03-01 11:32:37 bashnesnos

返答いただきありがとうございます。idsと日付が私のコントロールから外れていて、迷惑に順序が狂っています。そうでない場合は、日付に基づいて生成することをお勧めします。私はメモリの不確実性がハッシュマップを作るための要素であるので、私は2つの木にこだわるだけだと思う。私は数回リサイズしなければならない可能性が高い。 @HarrisonW。 –

。あなたは歓迎です:-)ハッシュマップを数回サイズ変更しても均衡のとれたツリーへの挿入よりも優れているので、私はまだツリーとハッシュマップを使うことをお勧めします。 – bashnesnos

TreeMapは、AVLの代替品であるRed-Black treeを実装しています。

出典

2017-02-28 21:45:04 Kiryl

（追加順にオブジェクトを格納して取得するか、またはlast access + O（1）の複雑さを持つすべての標準HashMap操作）で行うことができます。

より複雑な日付アクセスパターン（範囲、ポイントクエリ）が必要な場合は、リンクリストの代わりにskip listという同じ考えを使用できます。この場合、日付によるアクセスはO（logN）になります。

そして、同じ値（リンクされたリストやスキップリスト）をツリー上に構築し、idで値を設定するオプションもあります。

出典

2017-03-03 09:36:06 starikoff

答えて

関連する問題