18 citations · 72 across the 35 of their papers we have counts for
5 papers · 2 filters
In pursuit of the dynamic optimality conjecture
John Iacono
In 1985, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offlin…
Combining Binary Search Trees
Erik D. Demaine, John Iacono, Stefan Langerman +1
We present a general transformation for combining a constant number of binary search tree data structures (BSTs) into a single BST whose running time is within a constant factor of…
The Power and Limitations of Static Binary Search Trees with Lazy Finger
Prosenjit Bose, Karim Douïeb, John Iacono +1
A static binary search tree where every search starts from where the previous one ends (lazy finger) is considered. Such a search method is more powerful than that of the classic o…
The Fresh-Finger Property
John Howat, John Iacono, Pat Morin
The unified property roughly states that searching for an element is fast when the current access is close to a recent access. Here, "close" refers to rank distance measured among…
Why some heaps support constant-amortized-time decrease-key operations, and others do not
John Iacono
A lower bound is presented which shows that a class of heap algorithms in the pointer model with only heap pointers must spend Omega(log log n / log log log n) amortized time on th…