Peter Brass のAdvanced Data Structuresを読んでいます。
検索ツリーに関する章の冒頭で、彼は検索ツリーには 2 つのモデルがあると述べました。1 つはノードが実際のオブジェクト (ツリーが辞書として使用される場合の値) を含み、もう 1 つはすべてのオブジェクトが格納されている場所です。葉と内部ノードは比較専用です。
最初のモデルに対する 2 番目のモデルの利点は何ですか?
3551 次
4 に答える
9
データがリーフ ノードのみにあるバイナリ ツリーの大きな利点の 1 つは、データセットにない要素に基づいて分割できることです。
たとえば、可能性のあるデータセットが 0 ～ 100 万で、アイテムの大部分がハイエンドまたはローエンドのどちらかにあり、中間ではない場合でも、最初の比較を 500,000 と比較したい場合があります。私のデータセットにはありません。すべてのノードにデータがある場合、これはできません。理論的には通常は必要ありませんが、データの単純化された実装以外の値に基づいて分割することが何度もありました。
于 2010-10-14T18:15:46.440 に答える
3
B+ ツリーは、すべてのキー/値がリーフ ノードに格納されている場合の例です。ここでの主な利点は、すべてのアイテムがリーフ ノードにあるため、リーフ ノードをリンクしてリンク リストを形成できることです。特定の要素にアクセスすると、リーフ ノードが互いにリンクされているため、親にアクセスしなくてもシーケンス内の次の要素をいつでも見つけることができます。ファイルシステムとデータベースストレージシステムは、範囲検索などにこの構造を利用できます。
于 2011-11-29T11:07:09.527 に答える
1
いくつかの複雑な基準に基づいていくつかのオブジェクトにツリーを構築しているとしましょう。複数の物件から算出した一例。このオブジェクトを変更して計算値を保存できない場合があり、この条件の計算は広範囲に及びます。したがって、この条件を 1 回だけ計算し、条件の結果に基づいてオブジェクトをリーフに格納します。その後、ツリーが完成すると、パス内の各ツリー ノードの条件を計算する必要がないため、必要なオブジェクトをより迅速に見つけることができます。
于 2011-11-29T16:55:20.173 に答える
0
ノードに情報オブジェクトを適切に格納します。この場合はトライについて話しますが、情報を高速に取得するのに役立ちます (配列/ハッシュテーブルに格納するよりも高速で、最悪の場合の auf アクセスはトライで O(n) です)。これは O(m) [m は n の長さ])
ここを見てください: https://en.wikipedia.org/wiki/Trie
検索ツリーでは、この操作ははるかに複雑になる可能性があり (AVL Tree O(log n) を参照)、遅くなる可能性があり、実装がより適切になります。
どのデータ構造を選択する?? まあ、これはあなたが何をしたいかによって異なります
于 2010-10-14T18:15:12.367 に答える