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 (-5[1])uses the access lemma with appropriate choices of weights to show that it has the working set and static finger properties. (-5[1])This data structure is the subject of the dynamic optimality conjecture. Whenever a node is accessed in this data structure, it is subsequently brought to the root using a series of (*) zig-zig and zig-zag (10[1])operations, which are generalizations of the rotations used in AVL (-5[1])and red-black trees. For 10 points, name this binary search tree that is conjectured to perform as well as any possible tree. ■END■ (10[3])

Back to tossups