Packet 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 (15[1])algorithm. One data structure enforces (15[1])this property by ensuring its namesake (*) “factor” (10[1])always has a (10[1])magnitude of at most (10[1])1 for each (10[1])element. “Rotations” are used to automatically maintain this property (10[3])in AVL (10[1])and red-black examples of a certain data structure. (10[1])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