# Simple Algorithms for the On-Line Multidimensional Dictionary andRelated Problems

Report ID:
1998-22
Authors:
Teofilo F. Gonzalez
Date:
1998-08-01 05:00:00

## Abstract

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.