algorithm - O(log(n)) 中的优先级验证器实现

Question

优先级验证器支持操作、插入、删除和 not-all-bigger(z)。后一种操作输出“是”，前提是当前集合中有一个元素的键≤ z，否则输出“否”。z 由用户提供。当集合中有 n 个元素时，是否可以实现优先级验证器以使其操作具有摊销成本 o(log n)？

Answer 1

是的，使用平衡树，您有顺序，因此您可以通过沿着树中的左侧路径找到小于或等于 z 的元素，前往越来越小的元素，注意树的高度是对数的，所以它需要 O(logn)。所有其他操作也需要 O(logn)

Answer 2

不确定这个问题是否可以通过使用跳过列表来解决。由于插入/删除都是 log(n)，它总是可以保持集合中最大的家伙。