Question

In 2005, John Iacono introduced the concept of key-independent optimality and proved that this data structure has said property. The deque (“deck”) conjecture states that if this data structure is treated as a double-ended queue, then each operation takes amortized constant time. The paper that introduced this data structure uses the access lemma with appropriate choices of weights to show that it has the working set and static finger properties. This data structure is the subject of the dynamic optimality conjecture. Whenever (15[1])a node is accessed in this data structure, (15[1])it is subsequently brought to the root using a series of (-5[1])(*) zig-zig and zig-zag operations, (10[1])which are generalizations of the rotations used in AVL and red-black trees. (0[1]-5[1])For 10 points, name this binary search tree that is conjectured to perform as well as any possible tree. ■END■ (0[1])

Back to tossups