Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance

摘要

We introduce a new O(lg lg n)-competitive binary search tree data structure called poketree that has the advantage of attaining, under worst-case analysis, O(lg n) cost per operation, including updates. Previous O(lg lg n)-competitive binary search tree data structures have not achieved O(lg n) worst-case cost per operation. A standard data structure such as red-black tree or deterministic skip list can be augmented with the dynamic links of a poketree to make it O(lg lg n)-competitive. Our approach also uses less memory per node than previous competitive data structures supporting updates.