van Emde Boas 树的最大元素是否应该存储在树外？
我们不需要像对待最小元素一样对待最大元素吗？为什么我们可以在存在这种不对称性的情况下仍然在 0(loglogN) 时间内执行操作？最大元素沿着树传播，但最小元素却没有……相反的情况是否有可能有时间进行操作？
我在这里找到：http://code.google.com/p/libveb/wiki/Intro 我们需要存储它，因为元素的 sqrt 是一个耗时的操作。但我认为还有别的事情。
Don't we need to treat the max element similarly to the min element? Why we can have this asymmetry and still perform operations in 0(loglogN) time? The max element propagate down the tree but the min does not... Is it possible with the reversed case to have the time for operations?
I found here: http://code.google.com/p/libveb/wiki/Intro that we need to store it because the sqrt of element is time consuming operation. But I think that there is something else.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为操作员要问的是为什么我们不存储与最小元素类似的最大元素，即为什么我们将最大元素向下传播到树中以及这种处理是否不能逆转。
我们将 min 元素存储在树之外，因为它的存在表明该特定结构是非空的，这可以防止我们进行不必要的递归调用来检查是否为空，并使插入空树成为 O(1) 操作，即只需设置最小元素。我们需要树外的 max 和 min 元素来进行后继和前驱操作。
Erik Demaine 的讲义（由 templatetypedef 提供的链接）对此进行了很好的解释。
我相信应该可以将最小/最大元素保留在外面而不传播，并且仍然保持每次操作的 O(log log u) 时间，因为我们这样做只是为了知道结构是否非空。保留它们并且不将它们传播下去是多余的，并且不会为您赢得额外的时间。
I think what the op is asking is why are we not storing the max element similar to the min element i.e. why do we propagate the max element down into the tree and whether this treatment cant be reversed.
We store the min element outside the tree since its presence suggests that that particular structure is non-empty which prevents us from making an unnecessary recursive call to check for emptiness and makes insertion into an empty tree an O(1) operation i.e just set the minimum element. We need both max and min elements outside the tree for the successor and predecessor operations.
This is explained rather nicely in Erik Demaine's lecture notes (link provided by templatetypedef).
I believe it should be possible to keep either of the min/max elements outside without propagation and still maintain O(log log u) time per operation since we do this just to know if a structure is non-empty. Keeping both of them and not propagating both of them down is redundant and won't buy you extra time.
van Emde Boas 树通常会单独存储最大值和最小值，否则您无法有效地实现后继和前趋。
您是否看到过有其他暗示的具体来源？我见过的所有关于 vEB 树的注释都描述了以这种方式存储最大值和最小值。请参阅
希望这会有所帮助！
van Emde Boas trees do typically store the maximum and minimum values separately, since otherwise you cannot efficiently implement successor and predecessor.
Is there a specific source you've seen that suggests otherwise? All of the notes on vEB-trees that I have seen describe storing both the maximum and minimum values this way. See
Hope this helps!