Simple Algorithms for the On-Line Multidimensional Dictionary andRelated Problems

The on-line multidimensional dictionary problem consists of executing\\mbox{on-line} any sequence of the following operations: INSERT($p$),DELETE($p$) and MEMBERSHIP($p$), where $p$ is any (ordered) $d$-tuple (orstring with $d$ elements, or points in $d$-space where the dimensions have beenordered).We introduce a clean structure based on balanced binary search trees, which wecall multidimensional balanced binary search trees, to represent the set of$d$-tuples. We present algorithms for each of the above operations that take$O(d + \\log n)$ time, where $n$ is the current number of $d$-tuples in the set,and each INSERT and DELETE operation requires no more than a constant number ofrotations. Our structure requires $dn$ words to represent the input, plus$O(n)$ pointers and data indicating the first component where pairs of$d$-tuples differ.This information, which can be easily updated, enables us to test forMEMBERSHIP efficiently. Other operations that can be performed efficiently inour multidimensional balanced binary search trees are: print in lexicographicorder ($O(dn)$ time), find the (lexicographically) smallest or largest$d$-tuple ($O(\\log n)$ time), and concatenation ($O(d + \\log n)$ time).Finding the (lexicographically) $k^{th}$ smallest or largest $d$-tuple can alsobe implemented efficiently ($O(\\log n)$ time), at the expense of adding aninteger value at each node.