(2015) Greedy Is an Almost Optimal Deque.
Abstract
In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Pǎtraşcu (DHIKP) to accommodate for insertions and deletions. Within this extended model, we study the online Greedy BST algorithm introduced by DHIKP. Greedy BST is known to be equivalent to a maximally greedy (but inherently offline) algorithm introduced independently by Lucas in 1988 and Munro in 2000, conjectured to be dynamically optimal. With the application of forbidden-submatrix theory, we prove a quasilinear upper bound on the performance of Greedy BST on deque sequences. It has been conjectured (Tarjan, 1985) that splay trees (Sleator and Tarjan, 1983) can serve such sequences in linear time. Currently neither splay trees, nor other general-purpose BST algorithms are known to fulfill this requirement. As a special case, we show that Greedy BST can serve output-restricted deque sequences in linear time. A similar result is known for splay trees (Tarjan, 1985; Elmasry, 2004). As a further application of the insert-delete model, we give a simple proof that, given a set U of permutations of [n], the access cost of any BST algorithm is \(\Omega ( \log \vert U \vert + n)\) on “most” of the permutations from U. In particular, this implies that the access cost for a random permutation of [n] is \(\Omega {(n\log {n})}\) with high probability. Besides the splay tree noted before, Greedy BST has recently emerged as a plausible candidate for dynamic optimality. Compared…
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Depositing User: | Sebastian Weisgerber |
| Date Deposited: | 22 Feb 2018 11:11 |
| Last Modified: | 22 Feb 2018 16:06 |
| URI: | https://publications.cispa.saarland/id/eprint/1685 |
Actions
Actions (login required)
 |
View Item |