2

各要素にアクセスする確率がわからないが、一部の要素が他の要素よりもはるかに頻繁にアクセスされると確信している場合は、Splay treeを使用します。すべての確率がわかっている場合、何を使用すればよいですか? この場合、スプレイツリーよりも優れたデータ構造が必要であると思います。

あらゆるタイプの検索ツリーをいつ、どこで使用する必要があるかをすべて想像しようとしています。誰かがすべての検索ツリーの比較や類似の構造に関する記事へのリンクを投稿できますか?

編集私はまだO(log n)最悪のケースを望んでいますが、平均的にはより高速になるはずです。スプレー ツリーは良い例ですが、このツリーの構成を事前定義したいと思います。

たとえば、保存する要素の配列と、各要素にアクセスする頻度を定義する[a1, a2, .. an]各要素の確率があります。[p1, p2, .. pn]スプレイ ツリーを作成し、各要素をスプレイ ツリー ( O(n log n)) に追加し、指定された確率でそれらにアクセスして、目的のツリーを作成できます。したがって、確率がある場合[1/2, 1/4, 1/4]、最初の要素を広げて最初の要素にする必要があります。そのため、要素を確率で並べ替え、アクセス確率が低いものから高いものへと並べる必要があります。それもかかりO(n log n)ます。したがって、そのようなツリーを構築する全体の時間はO(n log n)大きな定数です。私の目標は、この数値を下げることです。

他のものを使用してもかまいませんが、検索ツリーは使用しませんが、Splay ツリーの場合よりも時間を短縮したいと考えています。そして、検索、挿入、削除がO(log n)償却の範囲内にあることを望みます。

4

3 に答える 3

2

編集:ツリーを動的に更新したいとは思いませんでした-以下のアルゴリズムでは、すべての要素と確率を事前に知る必要があります。そのような状況にある人が現れた場合に備えて、投稿を残しておきます。

たまたまCormenらによるIntroduction to Algorithmsの第3版を所有している場合は、すべての確率がわかっている場合に最適な二分探索木を作成するための動的計画法アルゴリズムについて説明しています。

アルゴリズムの大まかな概要は次のとおりです。まず、要素を (確率ではなく、要素の値で) 並べ替えます。どの要素がツリーのルートになるべきかはまだわかりませんが、ツリーのルートの左側にあるすべての要素がリストのその要素の左側にあり、その逆であることはわかっています。ルートの右側の要素。インデックスkの要素をルートとして選択すると、要素 0 からk-1および要素k+1からn-1に対して最適なツリーを構築する方法という 2 つのサブ問題が発生します。これらの問題を再帰的に解いて、ルートが要素kであるツリーでの検索の予想コストがわかるようにします。kのすべての可能な選択に対してこれを行います、どのツリーが最適かがわかります。計算時間を節約するために、動的計画法またはメモ化を使用します。

于 2012-08-10T09:40:48.380 に答える
1

ハッシュ テーブルを使用します。

順序付けられた反復の必要性について言及したことは一度もありません。これを犠牲にすることで、償却されたO(1)挿入/アクセスの複雑さを達成できますO(log n)。

具体的には、リンクされたリスト バケットでハッシュ テーブルを使用し、最前面への移動の最適化を使用します。これが意味することは、複数のアイテムでバケット (リンクされたリスト) を検索するたびに、見つかったアイテムをそのバケットの前に移動することです。次にこの要素にアクセスすると、すでに前面に表示されています。

アクセス確率が分かっている場合は、テクニックをさらに改良することができます。新しい要素をバケットに挿入するときは、前に挿入するのではなく、最も可能性の高い最初の順序を維持するように挿入します。move-to-front テクニックは、すでにこのソートを暗黙的に実行する傾向がありますが、より迅速にブートストラップするのに役立つことに注意してください。

于 2012-08-10T18:16:53.557 に答える
0

作成したツリーが変更されない場合は、おそらくハッシュ テーブルまたはタンゴ ツリーを使用する必要があります: http://en.wikipedia.org/wiki/Tango_tree

ハッシュ テーブルは、オーバーロードされていない場合は O(1) ルックアップであり、オーバーロードされた場合は O(n) に劣化します。

Tango ツリーは、一度構築されると、O(loglogn) ルックアップになります。削除または挿入はサポートされていません。

使用に適した「完全なハッシュ」として知られるものもあります。

于 2012-08-10T19:36:57.813 に答える