Answer the following about the Robert Tarjan and Daniel Sleator-created splay tree, for 10 points each.
[10e] Splay trees belong to a class of trees named for this algorithm, in which nodes less than the root are in the left subtree. This algorithm finds an element in a sorted array in O(log n) time by repeatedly comparing it to the middle.
ANSWER: binary search [accept binary search trees; prompt on search]
[10m] The “splay” operation executes “zig” and “zig-zag” steps by performing these operations to center the queried element. Self-balancing BSTs such as AVL trees perform “left” and “right” instances of these operations.
ANSWER: tree rotations [accept left rotation or right rotation]
[10h] The hypothetical runtime of a splay tree used as a deque is given by the minimum number of applications of this function of n that yields a constant. Tarjan proved that a sequence of operations on an union-find structure has runtime proportional to this function of the number of nodes.
ANSWER: inverse Ackermann function [prompt on a or alpha; reject “Ackermann function”]
<Science - Other Science - Computer Science>