max 要素を min 要素と同じように扱う必要はありませんか? この非対称性を持ちながら、0(loglogN) 時間で操作を実行できるのはなぜですか? 最大要素はツリーを下に伝播しますが、最小要素は伝播しません...逆のケースで操作の時間を確保することは可能ですか?
私はここで見つけました: http://code.google.com/p/libveb/wiki/Intro 要素の sqrt は時間のかかる操作であるため、それを保存する必要があります。しかし、私は何か他のものがあると思います。
op が求めているのは、min 要素と同様の max 要素を保存しない理由、つまり max 要素をツリーに伝播する理由と、この処理を元に戻すことができないかどうかだと思います。
ツリーの外側に min 要素を格納します。これは、特定の構造が空でないことを示しているため、空であることを確認するために不要な再帰呼び出しを行うことを防ぎ、空のツリーへの挿入を O(1) 操作にするためです。最小要素。後続操作と先行操作には、ツリーの外側にある max 要素と min 要素の両方が必要です。
これは、Erik Demaine の講義ノート (templatetypedef が提供するリンク) でかなりうまく説明されています。
構造が空でないかどうかを知るためだけにこれを行うため、最小/最大要素のいずれかを伝播せずに外部に保持し、操作ごとに O(log log u) 時間を維持することが可能であると考えています。それらの両方を保持し、両方を伝播しないことは冗長であり、余分な時間を稼ぐことはありません.
van Emde Boas ツリーは通常、最大値と最小値を別々に格納します。そうしないと、後継者と先行者を効率的に実装できないからです。
そうでないことを示唆する特定の情報源はありますか? 私が見た vEB ツリーに関するメモはすべて、この方法で最大値と最小値の両方を格納することを説明しています。見る
お役に立てれば！