O（log（n））中的優先級驗證器實現

Question

優先級驗證程序支持操作，插入，刪除和非全部更大（z）。後者操作輸出「是」，只要該集合中當前有key≤z的元素，否則爲「否」。 z由用戶提供。是否可以實施優先權驗證人，以便在該組中有n個要素時，其運作具有攤銷成本o（log n）？

Answer 1

是的，在平衡樹木的情況下，您有順序，所以您可以通過沿着樹中的左側路徑找到小於或等於z的元素，然後到更小和更小的元素，注意高度樹是對數的，所以它將花費O（logn）。所有其他操作也需要O（logn）

Answer 2

不知道這個問題是否可以通過使用跳過列表來解決。由於插入/刪除都是log（n），並且它可以始終保持集合中最大的人物。