Round 10: Tossup 18

A 2015 paper by Haeupler, Sen, and Tarjan relaxes this property in one data structure and uses an exponential potential function-based analysis to show that this property can be enforced in constant amortized time. Aragon and Seidel pioneered a hybrid-named data structure that uses a randomized strategy to enforce this property more efficiently. A pair of sorted linked lists are used to enforce this property periodically using the Day-Stout-Warren algorithm. One data structure enforces (15[1])this property by ensuring its namesake (*) “factor” always has a magnitude of at most 1 for each element. “Rotations” are used to automatically maintain this property in AVL (10[1])and red-black examples of a certain data structure. For 10 points, (-5[1])name this property of binary search trees whose left and right branches have similar heights. ■END■ (10[1]0[2])

Back to tossups

Buzzes

Summary