Quadtree

This article has an unclear citation style. The references used may be made clearer with a different or consistent style of citation and footnoting. (April 2015) (Learn how and when to remove this message)

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. The data associated with a leaf cell varies by application, but the leaf cell represents a "unit of interesting spatial information".

The subdivided regions may be square or rectangular, or may have arbitrary shapes. This data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974.^[1] A similar partitioning is also known as a Q-tree.

All forms of quadtrees share some common features:

• They decompose space into adaptable cells.
• Each cell (or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits.
• The tree directory follows the spatial decomposition of the quadtree.

A tree-pyramid (T-pyramid) is a "complete" tree; every node of the T-pyramid has four child nodes except leaf nodes; all leaves are on the same level, the level that corresponds to individual pixels in the image. The data in a tree-pyramid can be stored compactly in an array as an implicit data structure similar to the way a complete binary tree can be stored compactly in an array.^[2]