3

ノードに対して次の定義を持つバイナリ ツリーがあるとします。 


struct node
{
 int key1 ;
 int key2 ;
}

二分探索木は、key1 に基づいて作成されます。O(1) 空間の key2 に基づいて二分探索木を再配置できるようになりました。ノードへのポインターの配列を使用して、変数空間でこれを行うことができますが。

私がこれを必要とする実際の問題は、「ファイル内の一意の単語の出現回数を数え、頻度の高い順に結果を表示する」ことです。ここで、BST ノードは 


{
 char *word;
 int freq ;
}
BST は最初に単語のアルファベット順に基づいて作成され、最後に freq に基づいて作成されます。

データ構造、つまり BST の選択が間違っていますか?

4

6 に答える 6

1

マップ、BSTは、辞書の出力を並べ替える必要がある場合に適しています。

また、追加、削除、ルックアップの操作を混同する必要がある場合に適しています。これはここでのあなたの必要性ではないと思います。辞書を読み込んで並べ替えてから、検索するだけですよね？この場合、ソートされた配列がおそらくより良いコンテナです。（ ScottMeyerのEffectiveSTLの項目23を参照してください）。
（更新：配列はメモリ内でデータを連続して取得し、マップ内の各ノードにはマップ内の他のノードへの2つのポインターが含まれているため、マップはソートされた配列よりも多くのメモリキャッシュミスを生成する可能性があることを単純に考慮してください。シンプルでメモリ内のスペースをあまりとらないので、ソートされたベクトルの方がおそらく良いオプションです。マイヤーの本からその項目を読むことを強くお勧めします）

あなたが話しているソートの種類については、stlからのそのアルゴリズムが必要になります： stable_sort。アイデアは、辞書を並べ替えてから、頻度キーでstable_sort（）を使用して並べ替えることです。

それはそのようなものを与えるでしょう（実際にはテストされていませんが、あなたはアイデアを得ました）：

struct Node
{
char * word;
int key;
};

bool operator < (const Node& l, const Node& r)
{
    return std::string(l.word) < std::string(r.word));
}

bool freq_comp(const Node& l, const Node& r)
{
    return l.key < r.key;
}

std::vector<node> my_vector;
... // loading elements
sort(vector.begin(), vector.end());
stable_sort(vector.begin(), vector.end(), freq_comp);
于 2009-08-13T13:43:34.010 に答える
1

freqソートされた新しいツリーを作成し、古いツリーからそれらをポップするすべての要素をそこにプッシュできると思います。

それはO(1)かもしれO(log N)ませんが、とにかく大きくない方が似ている可能性があります。

また、C# でどのように呼び出すかはわかりませんが、Python では list を使用できますが、2 つの異なるキーで並べ替えることができます。

于 2009-08-14T01:10:15.990 に答える
1

これは、新しいキーに基づいてツリーのバランスを再調整するための私の提案です (まあ、2 つの提案があります)。

最初のより直接的な方法は、Heapsort の「バブルアップ」機能を何らかの方法で適応させることです (Sedgewick の名前を使用するため)。ここにウィキペディアへのリンクがあります。彼らはそれを「ふるいにかける」と呼んでいます。完全にバランスの取れていないツリー (これが必要です) 用に設計されたわけではありませんが、ツリーのインプレース並べ替えの基本的な流れを示していると思います。ツリーは実際にはツリーではなく配列に格納されているため、従うのは少し難しいかもしれません (ただし、ある意味でのロジックではツリーとして扱われます) --- おそらく、そのような配列ベースの表現力最高！知るか。

私のよりクレイジーな提案は、スプレイツリーを使用することです。彼らは気の利いたものだと思います。ここにwiki リンクがあります。基本的に、どの要素にアクセスしても一番上に「バブルアップ」されますが、BST の不変条件は維持されます。したがって、最初のツリーを構築するために元の Key1 を維持しますが、「より高い頻度」の値のほとんども上部にあることを願っています。これは十分ではないかもしれません (それが意味するのは、より高い頻度の単語がツリーの「近く」にあるということだけであり、必ずしも何らかの順序で並べられているわけではありません)。バランシング アルゴリズムを使用すると、そのようなスプレイ ツリーでより高速に実行される可能性があります。

お役に立てれば！そして、興味深いなぞなぞをありがとう、これは私にとって良い Haskell プロジェクトのように思えます..... :)

于 2009-08-13T16:32:37.587 に答える
1

これは O(1) 空間で簡単に実行できますが、O(1) 時間ではできません ;-)

再ソートされるまでツリー全体を再帰的に再配置することは可能に思えますが、おそらくそれほど高速ではありません。せいぜい O(n) かもしれませんが、実際にはもっと悪いかもしれません。そのため、ツリーの作成が完了したらすべてのノードを配列に追加し、この配列を頻度 (平均で O(log n) になります) でクイックソートを使用して並べ替えると、より良い結果が得られる場合があります。少なくともそれは私がすることです。余分なスペースが必要な場合でも、ツリーを元の位置に再配置するよりも有望に思えます。

于 2009-08-13T16:45:02.447 に答える
0

考えられる 1 つのアプローチは、2 つのツリーを構築することです。によって索引付けされたものword、 によって索引付けされたものfreq。

ツリー ノードにデータ ノードへのポインタwordが含まれている限り、 に基づくツリー経由でアクセスして情報を更新し、後で にfreq基づくツリーでアクセスして出力することができます。

ただし、速度が本当に重要な場合は、キーとしての文字列を取り除くことを検討しています. 文字列比較は非常に遅いことで知られています。

速度が重要でない場合は、yves が提案したように、に基づいてデータを収集し、に基づいてword再ソートすることをお勧めします。freq

于 2009-08-13T13:55:37.777 に答える