Title: The Hidden Binary Search Tree:A Balanced Rotation-Free Search Tree in the AVL RAM Model,
Abstract: In this paper we generalize the definition of "Search Trees" (ST) to enable
reference values other than the key of prior inserted nodes. The idea builds on
the assumption an $n$-node AVL (or Red-Black) requires to assure $O(\log_2n)$
worst-case search time, namely, a single comparison between two keys takes
constant time. This means the size of each key in bits is fixed to $B=c\log_2
n$ ($c\geq1$) once $n$ is determined, otherwise the $O(1)$-time comparison
assumption does not hold. Based on this we calculate \emph{ideal} reference
values from the mid-point of the interval $0..2^B$. This idea follows
`recursively' to assure each node along the search path is provided a reference
value that guarantees an overall logarithmic time. Because the search tree
property works only when keys are compared to reference values and these values
are calculated only during searches, we term the data structure as the Hidden
Binary Search Tree (HBST). We show elementary functions to maintain the HSBT
height $O(B)=O(\log_2n)$. This result requires no special order on the input --
as does BST -- nor self-balancing procedures, as do AVL and Red-Black.