問題タブ [van-emde-boas-trees]

vEBツリーの信頼できるC++実装はありますか？

Boostにはありません。かなり珍しいようです。

vEBツリーまたはy-fastトライまたは同様のデータ構造用の（おそらく商用の）ライブラリはありますか？

vEB ツリーの概念を理解しようとしていました。

例: ユニバース セット U = {0, 1, 2, 3 ..... 8} を仮定しました。なのでサイズは9号。

ここで、サブセット S = {0, 1, 3, 4, 6, 7} を取ります。

オペレーションの場合、FindSuccessor (3, S); サブセット S で 3 を超える最小の要素を知る必要がある場合、要素の上位ビットと下位ビット、つまり 3 を知る必要があります。

1つの説明は、前半と後半のビットであり、結果00と11をそれぞれハイとローとして与えます。

別の言い方：

高 = 床 [要素/平方(|U|)] = 床 [3/平方 (9)] = 床 [1] = 1;

低 = 要素 % sqrt(|U|) = 3 % sqrt (9) = 0;

どこが間違っているのか説明してください。

max 要素を min 要素と同じように扱う必要はありませんか? この非対称性を持ちながら、0(loglogN) 時間で操作を実行できるのはなぜですか? 最大要素はツリーを下に伝播しますが、最小要素は伝播しません...逆のケースで操作の時間を確保することは可能ですか?

私はここで見つけました: http://code.google.com/p/libveb/wiki/Intro 要素の sqrt は時間のかかる操作であるため、それを保存する必要があります。しかし、私は何か他のものがあると思います。

整数の高速優先キュー以外に、 van Emde Boasツリーのアプリケーションはありますか？

van Emde Boas ツリーを実装していますが、コンストラクターで再帰を使用すると非常に便利な状況に遭遇しました。

ツリーにルート ノードを作成すると、そのノードは他の多くのノードへのポインタを持ち、それらのノードは他の多くのノードを指すようになります。これらが null データで初期化されていても、すべてそこにある必要があります。

編集:コメントへの回答として、メモリを割り当てるときは常に注意する必要があるため、悪い習慣かもしれないと思いました。この場合、ユーザーはそのような新しいノードを割り当てることによる影響を認識していない可能性があるため、意図したよりも多くのメモリを割り当てる可能性がありますか? それ以外は、コンストラクターでメモリを割り当てるのは奇妙/危険に思えたと思います。

このコードは、完全なツリーが作成されるまで、新しいノードを再帰的に作成します。これは悪い習慣ですか？もしそうなら、Javaでそれを行うより良い方法はありますか?