1. ホーム
  2. data-structures

[解決済み] ハッシュテーブルに対するバイナリサーチツリーの優位性

2022-09-09 10:30:32

疑問点

ハッシュテーブルに対するバイナリサーチツリーの利点は何ですか?

ハッシュテーブルはシータ(1)時間で任意の要素を検索でき、要素を追加するのも同じくらい簡単です...が、その逆の利点はよくわかりません。

どのように解決するのですか?

バイナリサーチツリー(参照ベース)はメモリ効率に優れていることを忘れないでください。必要以上にメモリを確保することはありません。

例えば、あるハッシュ関数が範囲 R(h) = 0...100 を持つ場合、たとえ 20 個の要素をハッシュ化するだけであっても、100 個の (ポインタへの) 要素の配列を割り当てる必要があります。同じ情報を保存するためにバイナリ検索ツリーを使用する場合、必要なだけのスペースと、リンクに関するいくつかのメタデータを割り当てるだけです。