Skip-Splay: Toward Achieving the Unified Bound in the Binary Search Tree Model
Sep 30, 2009
Abstract:
A simple lower bound shows that a binary search tree algorithm must pay Omega(lg n) per query in the worst case, and this bound can be achieved with a balanced binary search tree. However, in practice, a query sequence may contain a substantial amount of nonrandomness that can be exploited to speed up search. This speedup can be formalized by using an input-sensitive function to bound the cost an algorithm pays to execute a sequence of queries. An example of such a bound is the Unified Bound of Iacono, which essentially states that the cost of querying an element is low when it is near to a recently queried element. We present skip-splay, the first binary search tree algorithm known to have a running time that nearly achieves the Unified Bound, UB(s), on a sequence of queries s = s_1,...,s_m to members of {1,...,n}. Skip-splay trees require only O(m lg lg n + UB(s)) time to execute a query sequence, and the skip-splay algorithm is both simple and similar to the splay algorithm.div>
A simple lower bound shows that a binary search tree algorithm must pay Omega(lg n) per query in the worst case, and this bound can be achieved with a balanced binary search tree. However, in practice, a query sequence may contain a substantial amount of nonrandomness that can be exploited to speed up search. This speedup can be formalized by using an input-sensitive function to bound the cost an algorithm pays to execute a sequence of queries. An example of such a bound is the Unified Bound of Iacono, which essentially states that the cost of querying an element is low when it is near to a recently queried element. We present skip-splay, the first binary search tree algorithm known to have a running time that nearly achieves the Unified Bound, UB(s), on a sequence of queries s = s_1,...,s_m to members of {1,...,n}. Skip-splay trees require only O(m lg lg n + UB(s)) time to execute a query sequence, and the skip-splay algorithm is both simple and similar to the splay algorithm.div>