Erik D. Demaine, Dion Harmon, John Iacono, Scu Dynamic Optimality, Jacob Holm, Kristian De Lichtenberg, ...
Advanced topics in data structures: bibliography list #3
Dynamic Optimality–Almost (2008)
Erik D. Demaine, Dion Harmon, John Iacono
We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan’s...
Dynamic Optimality–Almost (2008)
Erik D. Demaine, Dion Harmon, John Iacono
Abstract. We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and...
Dynamic Optimality–Almost (2008)
Erik D. Demaine, Dion Harmon, John Iacono
We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan’s...
Dynamic Optimality–Almost (2008)
Erik D. Demaine, Dion Harmon, John Iacono
We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan’s...
New bounds on optimal binary search trees (2006)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2006.
New bounds on optimal binary search trees (2006)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2006.
New Bounds on Optimal Binary Search Trees (2006)
Dion Harmon, Erik Demaine, Rodolfo Ruben Rosales, Pavel I. Etingof, Dion Harmon
New bounds on optimal binary search trees / (2006)
Binary search trees (BSTs) are a class of simple data structures used to store and access keys from an ordered set. They have been around for about half a century. Despite their ubiquitous use in...