The Hidden Binary Search Tree

  • Saulo Queiroz
  • Edimar Bauer

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(log2 n) worst-case search, namely, comparison between keys takes constant time. Therefore the size of each key in bits is fixed to B = O(log2 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..2B. 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.

Publicado
26/07/2018
QUEIROZ, Saulo; BAUER, Edimar. The Hidden Binary Search Tree. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3160.