What Is a Quadtree?

A quadtree is a tree-like structure based on the power of four and used to organize files in a database. Each parent, or starting, node has four child nodes, and each child holds a certain amount of data. When the data limit spills over its boundary, four children will be made from that node. There are two main quadtree structures: the region and point tree, each slightly different in design. While a quadtree is most often used with databases, it also can be used to find pixels in two-dimensional (2D) images, because the pixels in a 2D image can always be separated into four parts.

All tree-like structures are made with parent, or branch, nodes and child, or leaf, nodes. The parent is the starting point and contains broad category-based data, while the child holds files and documents. In a quadtree, every parent must have four children. While there must be four children, not all children have to contain data; those without are known as null nodes. These null nodes often remain stagnant and wait for data.

Each child node in a quadtree has a data limit. This limit is usually defined by the overall database size. When there is so much information that it pushes beyond the limit, the child node becomes a parent node by essentially giving birth — creating four child nodes that take up all the extra data. There will usually be one or two null nodes from this creation, but this depends entirely on how much data were in the node.

There are two main quadtrees: region and point. The region quadtree is used to decompose an entire 2D region into parts based on the power of four — such as four, eight or 16 parts — and often used for representations. This structure is best for images, or data field graphs. The point version is like a binary tree and is best used with ordered points. This variant also is a true tree, because there is a central point from which all the nodes spring, unlike the region version in which the nodes are scattered.

The most common use of the quadtree is to separate and organize a database, but this is not its only use. Algorithms made to find a specific pixel in an image commonly use quadtrees, because each pixel in an image can be separated into four equal parts. This makes quadtrees uniquely suited to searching out pixels.