Journals Proceedings

Abstract

In 1989 Wilber [2] conjecture a lower bound O (log n) for a query using any balanced existing binary search tree with static data. Later in 2004 Demaine et al.., [1] Came up with new lower bound O (loglogn) called interleave lower bound and he also claimed that these two lower bound O (log n) and O (loglogn) acts as a good tight intervals for any binary search tree. Tango tree was recently introduced by Demaine et al., [1], having O (loglogn) - competitive ratio. Tango tree [1] supports only lookup (search) operations, where most of the online algorithms (like dictionary problem, a cache problem, adaptive data compression, etc.,) need additions and removals of collections (key, value) too, which are not supported by tango trees [1]. In this paper, we propose a new upgraded version of tango tree which supports addition and removal of collections (key, value) dynamically without knowing the sequence before hand in O (loglogn) time. We show run-time analysis with experimental results. We also show theoretically how these algorithms achieve O (loglogn) -competitive dynamic interleave bound.