The Hidden Binary Search Tree

• Saulo Queiroz UTFPR
• Edimar Bauer UTFPR

DOI: https://doi.org/10.5753/etc.2018.3160

Resumo

In this paper we review and enhance the Hidden Binary Search Tree (HBST) presented in [Queiroz 2017]. The HBST idea builds on the assumption an n-node self-balanced tree (e.g. AVL) requires to assure O(log₂ n) worst-case search, namely, comparison between keys takes constant time. Therefore the size of each key in bits is fixed to B = O(log₂ n) once n is determined, otherwise the O(1)-time comparison assumption does not hold. HBST generalizes the searchtree property such that the position of a node in the tree results from comparing its key against ‘ideal’ reference values associated to its ancestors. The first ideal values comes from the mid-point of the interval 0..2^B. The strategy follows recursively such that the HBST height is bounded by O(B) regardless the input sequence of keys nor self-balancing procedures. In this paper we enhance the HBST to enable keys with arbitrary number of bits.

Referências

Adelson-Velsky, G. M. and Landis, E. M. (1962). An algorithm for the organization of information. In Proceedings of the USSR Academy of Sciences, volume 146, pages 263–266.

Guibas, L. J. and Sedgewick, R. (1978). A dichromatic framework for balanced trees. In 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), pages 8–21.

Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA.

Queiroz, S. (2017). The hidden binary search tree: A balanced rotation-free search tree in the AVL RAM model. CoRR, abs/1711.07746.