Árvore binária de pesquisa oculta com crescimento dinâmico

Abstract

The hidden binary search tree (HBST) is a data structure that proposes an alternative definition for the search property of binary search trees. In the HBST, the search path is determined by the mean value of the keys interval. If Β represents the minimum amount of bits to uniquely represent every possible key, the largest interval is [0.2Β[, which leads to an Ο(Β) height. However, HSBT does not support linear-time in-order traversal. In this work we present the Sorted HBST (SHBST), a data structure that satisfies not only the hidden search property but also the traditional binary search tree property. This works also presents a procedure (named Enhanced Propagation) to improve the height of HSBT by one unit. Also, the work discusses different methods to enable the dynamic growth of HBST and presents the Dynamic HSBT. All discussed structures were evaluated along with the AVL search tree. The results suggest that all studied structures present the same asymptotic efficiency.