具体的には、ハッシュテーブルではなくAVLツリーを使用した方が効率的に実行できる操作はありますか？
8889 次
2 に答える
5
私は通常、ハッシュテーブルよりもAVLツリーを好みます。ハッシュテーブルの予想時間O（1）の複雑さは、AVLツリーの保証時間O（log n）の複雑さを上回っていることを私は知っていますが、実際には、一定の要因により2つのデータ構造が一般的に競争力があり、気になる心配はありません。悪い振る舞いを引き起こすいくつかの予期しないデータ。また、プログラムのメンテナンス期間中に、ハッシュテーブルの最初の選択が正しいと思われる状況で、データを並べ替えた順序で必要とすることがよくあります。そのため、プログラムを書き直して、ハッシュテーブルの代わりにAVLツリー。それを十分な回数行うと、AVLツリーから始めた方がよいことがわかります。
キーが文字列の場合、3値検索は、AVLツリーまたはハッシュテーブルの合理的な代替手段を提供します。
于 2012-01-12T18:46:59.573 に答える
0
もちろん、明らかな違いは、AVLツリー（および他のバランスの取れたツリー）を使用すると、永続性を持つことができることです。O（log N）の時空間でツリーから要素を挿入/削除でき、最終的には新しい木だけでなく、古い木を維持することもできます。
ハッシュテーブルを使用すると、通常、O（N）未満の時間と空間でそれを行うことはできません。
もう1つの重要な違いは、キーに必要な操作です。AVLtressにはキー<=間の比較が必要ですが、ハッシュテーブル=には関数だけでなく比較も必要hashです。
于 2016-04-05T16:56:14.273 に答える