AVLツリーはいつハッシュテーブルより優れていますか？

具体的には、ハッシュテーブルではなくAVLツリーを使用すると、より効率的に実行できる操作はありますか？AVLツリーはいつハッシュテーブルより優れていますか？

2012-01-12 Matt

質問はあまりにも曖昧すぎて徹底的に答えられていません。これは、ハッシュテーブルの実装に大きく依存しますが、検索操作は、ハッシュテーブルと比べて、ツリー内ではるかに高速です。また、共通の接頭辞を持ついくつかのキーの検索は、ハッシュテーブル（ - >プロセッサキャッシュ）よりもあらゆる種類のツリーではるかに高速であることが保証されています。挿入/削除操作は、高さの制約と再調整のために効率的ではない可能性が高いですが、ハッシュテーブルはハッシュ全体を再構築するまでは簡単ではありません（→実装）。 – Damon

いいえ、ハッシュテーブルがサポートできない操作を考慮しない限り。順序を保ち、重複したキーをサポートするように。これを行う必要はありませんが、ハッシュテーブルを基本的に速くするものです。 –

ありがとう、それらのポイントは私が探していたものです。申し訳ありませんが質問がひどく言われた場合。 – Matt

私は一般に、ハッシュテーブルにAVLツリーを使用します。私はハッシュテーブルの予想時間O（1）の複雑さがAVLツリーの保証されたO（log n）複雑さに打ち勝つことを知っていますが、実際には一定の要因によって2つのデータ構造が一般的に競争しやすくなります。悪い行動を引き起こす予期しないデータまた、プログラムのメンテナンス期間中に、ハッシュテーブルの最初の選択が正しいと思われる状況で、ソート順にデータが必要な場合があることがよくありますので、プログラムを書き直してハッシュテーブルの代わりにAVLツリー。十分な時間を過ごしてください。あなたはAVLツリーから始めることもできます。

キーが文字列の場合、三項検索はAVLツリーやハッシュテーブルの代わりになります。

出典

2012-01-12 18:46:59 user448810

明らかな違いは、当然のことながら、AVL木（および他のバランス木）に、あなたは持続を持つことができるということです：あなたが挿入/ Oのツリーから要素を削除することができますスペース・アンド・（Nを記録）新しい木だけでなく、古い木を保つようにしてください。

ハッシュテーブルでは、一般に、O（N）以下の時間と空間では実行できません。

出典

2016-04-05 16:56:14 Stefan

AVLツリーはいつハッシュテーブルより優れていますか？

答えて

関連する問題