Title :
Dynamic optimality - almost [competitive online binary search tree]
Author :
E.D. Demaine;D. Harmon;J. Iacono;M. Patrascu
Author_Institution :
Comput. Sci. & Artificial Intelligence Lab., MIT, Cambridge, MA, USA
fDate :
6/26/1905 12:00:00 AM
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 Tarjan´s dynamic optimality conjecture of 1985 that O(1)-competitive binary search trees exist.
Keywords :
"Binary search trees","Data structures","Computer science","Tree data structures","Artificial intelligence","Laboratories","Information science","Read-write memory"
Conference_Titel :
Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on
Print_ISBN :
0-7695-2228-9
DOI :
10.1109/FOCS.2004.23
