Page "Z-order curve" Paragraph 33

Rather than building a pointer based quadtree, the points can be maintained in sorted order in a data structure such as a binary search tree.

This allows points to be added and deleted in O ( log n ) time.

Two quadtrees can be merged by merging the two sorted sets of points, and removing duplicates.

Point location can be done by searching for the points preceding and following the query point in the sorted order.

If the quadtree is compressed, the predecessor node found may be an arbitrary leaf inside the compressed node of interest.

In this case, it is necessary to find the predecessor of the least common ancestor of the query point and the leaf found.