Skip-Splay: Toward Achieving the Unified Bound in the BST Model

摘要

We present skip-splay, the first binary search tree algorithm known to have a running time that nearly achieves the unified bound. Skip-splay trees require only O(mlglgn+UB(σ)) time to execute a query sequence σ=σ{sub}1...σ{sub}m. The skip-splay algorithm is simple and similar to the splay algorithm.