我们不需要像对待 min 元素一样对待 max 元素吗？为什么我们可以有这种不对称性并且仍然在 0(loglogN) 时间内执行操作？最大元素沿树传播，但最小元素不会...反转的情况是否有可能有时间进行操作？
我在这里找到：http ://code.google.com/p/libveb/wiki/Intro 我们需要存储它，因为元素的 sqrt 是耗时的操作。但我认为还有别的东西。
问问题
727 次
2 回答
4
我认为操作要问的是为什么我们不存储类似于最小元素的最大元素，即为什么我们将最大元素向下传播到树中，以及这种处理是否不能逆转。
我们将 min 元素存储在树之外，因为它的存在表明该特定结构是非空的，这可以防止我们进行不必要的递归调用来检查是否为空，并使插入空树成为 O(1) 操作，即只需设置最小元素。我们需要树外的最大和最小元素来进行后继和前驱操作。
这在 Erik Demaine 的讲义中得到了很好的解释（链接由 templatetypedef 提供）。
我相信应该可以将任何一个最小/最大元素保留在外部而不进行传播，并且仍然保持每次操作的 O(log log u) 时间，因为我们这样做只是为了知道结构是否为非空。保留它们并且不传播它们是多余的，不会为您赢得额外的时间。
于 2013-03-25T02:46:28.207 回答
1
van Emde Boas 树通常会分别存储最大值和最小值，否则您将无法有效地实现后继和前驱。
有没有你见过的特定来源表明其他情况？我看到的所有关于 vEB 树的注释都描述了以这种方式存储最大值和最小值。看
希望这可以帮助！
于 2012-02-04T21:33:50.377 回答