Journals Proceedings

International Journal of Advances in Computer Science and Its Applications

Upgraded Tango Tree to solve the Dictionary Problem and its Applications



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.

No fo Author(s) : 2
Page(s) : 335 – 339
Electronic ISSN : 2250 - 3765
Volume 2 : Issue 3
Views : 484   |   Download(s) : 141