International Journal of Advances in Computer Science and Its Applications
Author(s) : SUNEETA AGARWAL, V S ANIRUDHA KAKI
In 1989 Wilber  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..,  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., , having O (loglogn) - competitive ratio. Tango tree  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 . 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.