Round 11: 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 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 (10[1])in AVL and red-black examples of a certain data structure. For 10 points, name this property of binary search trees whose left and right branches have similar heights. ■END■

Back to tossups

Buzzes

Summary