Dynamic z-fast tries

We describe a dynamic version of the z-fast trie, a new data structure inspired by the research started by the van Emde Boas trees and followed by the development of y-fast tries. The dynamic z-fast trie is a very simple, uniform data structure: given a set S of n variable-length strings, it is formed by a standard compacted trie on S (with two additional pointers per node), endowed with a dictionary of size n−1. With this simple setup, the dynamic z-fast trie provides predecessors/successors in time O(log max{ |x|, |x+|, |x-| }) (x± is the successor/predecessor of x in S) for strings of length linear in the machine-word size w. Prefix queries are answered in time O(log|x|+k), and range queries in time O(log max{ |x|, |y|, |x-|, |y+| }+k), where k is the number of elements in the output and x (and y) represent the input of the prefix (range) queries. Updates are performed within the same bounds in expectation (or with high probability using an appropriate dictionary). We then show a simple modification that makes it possible to handle strings of length up to 2^w; in this case, predecessor/successor queries and updates are supported in O(|x|/w + log max{ |x|, |x+|, |x-| }) time, (and O(|x|/B + log max{ |x|, |x+|, |x-| }) I/Os in the cache-oblivious model) with high probability. The space occupied by a dynamic z-fast trie, beside that necessary to store S, is just of 12n pointers, n integers and, in the “long string” case, O(n) signatures of O(w) bits each.