Load-Balancing Succinct B Trees

04/18/2021
by   Tomohiro I, et al.
0

We propose a B tree representation storing n keys, each of k bits, in either (a) nk + O(nk / n) bits or (b) nk + O(nk n/ n) bits of space supporting all B tree operations in either (a) O( n ) time or (b) O( n / n) time, respectively. We can augment each node with an aggregate value such as the minimum value within its subtree, and maintain these aggregate values within the same space and time complexities. Finally, we give the sparse suffix tree as an application, and present a linear-time algorithm computing the sparse longest common prefix array from the suffix AVL tree of Irving et al. [JDA'2003].

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset