如何在平衡的二叉树中保持最小和最大的O(1)时间，而不使用指针？

Question

“算法设计手册”中的3-7部分写道：

假设您可以访问平衡的字典数据结构，该结构支持O(log )时间内的每个操作搜索、插入、删除、最小、最大、后继和前任操作。解释如何修改insert和delete操作，以便它们仍然需要O(log )，但现在最小和最大占用O(1)时间。(提示：考虑使用抽象字典操作，而不是使用指针之类的。)

没有暗示，我认为这个问题相当容易。

这是我的解决方案：

对于树，我只维护一个指针min总是指向最小，另一个指针最大值总是指向最大值。

当插入x时，我只是比较min.key和x.key，if min.key > x.key, then min = x;，如果有必要的话，也可以对max进行比较。

删除x时，if min==x, then min = successor(x); if max==x, then max = predecessor(x);

但暗示说我不能胡搞指南针之类的东西。我的解决方案有指针吗？

如果我们不能使用额外的分数，我如何才能得到O(1)的最小和最大？

谢谢

Answer 1

您的答案与我给出的答案相同--您不是在乱搞指针，而是存储min/max值。

所以，只需更加自信:)

Answer 2

您可以通过使用Max堆实现log(N)更新/删除时间和获取最小/最大值的恒定时间

Answer 3

我不认为你能得到O(1)的最大值和最小值。

不管怎样，这本书想让你自己去发现二进制堆。如果你想自己做的话，不要看链接。只需考虑以下提示：“树的根始终包含最小值”(如果希望“最大值”为O(1)，则为最大值)。