The data structure used in building Treemap 2000 was
augmented k-d tree. Below is a little diagram of the
K-D tree. I augmented the k-d tree with a linked lists
of children of a particular nodes, and parent pointers.
It is possible to implement optimizations on this tree,
in order to fit different kind of applications. The
detailed explanations of K-D tree can be found any where.