Change search
ReferencesLink to record
Permanent link

Direct link
Greedy is an almost optimal deque
Show others and affiliations
2015 (English)In: 14th International Symposium on Algorithms and Data Structures, WADS 2015, Springer, 2015, 152-165 p.Conference paper (Refereed)Text
Abstract [en]

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 Ω(log |U| + n) on “most” of the permutations from U. In particular, this implies that the access cost for a random permutation of [n] is Ω(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 to splay trees, much less effort has gone into analyzing GREEDY BST. Our work is intended as a step towards a full understanding of GREEDY BST, and we remark that forbidden-submatrix arguments seem particularly well suited for carrying out this program.

Place, publisher, year, edition, pages
Springer, 2015. 152-165 p.
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9214
Keyword [en]
Algorithms, Data structures, Forestry, Access cost, Binary search trees, Dynamic optimality, Extended model, High probability, Insertions and deletions, Quasi-linear, Random permutations, Binary trees
National Category
Control Engineering
URN: urn:nbn:se:kth:diva-181504DOI: 10.1007/978-3-319-21840-3_13ScopusID: 2-s2.0-84951865390ISBN: 9783319218397OAI: diva2:900563
5 August 2015 through 7 August 2015

QC 20160204

Available from: 2016-02-04 Created: 2016-02-02 Last updated: 2016-02-04Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Saranurak, Thatchaphol
By organisation
Theoretical Computer Science, TCS
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 14 hits
ReferencesLink to record
Permanent link

Direct link