1. ホーム
  2. data-structures

[解決済み] フュージョンツリーを理解する?

2022-02-24 14:41:58

質問

私は、偶然にも ウィキペディアのページ を紹介しました。

フュージョンツリー

そして、一番下にリンクされているクラスノートのpdfを読みましたが、データ構造そのものについて手探りになり、かなり詳細に sketch(x) 関数を使用します。 私の混乱の一因は、論文が非常に一般的なことを言おうとしていることで、私は可視化するための具体例が欲しいのだと思います。

このデータ構造は、任意の32ビットまたは64ビット整数のキーに基づくデータを格納するのに適していますか? B-treeとどう違うのですか? 基本的にはB-treeに分岐要素を加えたものである、と書かれている部分があります。 B = (lg n)^(1/5) . 32ビットのキーを持つ完全実装のツリーの場合、Bは2になります。 これは単に2分木になるのでしょうか? このデータ構造は、もっと長いビット列をキーとして使うことを想定しているのだろうか?

ググってもあまり有用なものは出てきませんでしたが、このトピックに関する良いリンクがあれば歓迎します。 これは本当に単なる好奇心で、だから、私は以下のサイトでPDFにお金を払う気はない。 portal.acm.org まだです。

解決方法は?

セミナルペーパーを(ざっと)読みましたが、面白そうですね。 また、最初のページであなたの質問のほとんどに答えています。

論文は以下からダウンロードできます。 こちら

HTH!