Quadtree split operation

Question

I have trouble understanding the quadtree split operation. Say the maximum number of items a node can hold is 2; when we add a third element we create four sub-nodes. The question is, does the parent node keep its 2 items and the one who caused the overflow is inserted in a child-node or all three nodes are inserted in the sub-nodes?

Answer 1

All three nodes get inserted into a child node. Only the leaves node can hold some data in a tree.

This can make a difference with say, for example, kd-tree, where the space partition is more data oriented instead of fixed space partitioning, thus saving memory. On the other hand, fixed space partitions are easier to handle and can even be precomputed for even faster access.