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 (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 (10[1])operations, (10[1])which are generalizations of the rotations used in AVL (-5[1])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■ (10[3]0[1])

Buzzes

Summary