A quad tree, sometimes quadtree, Q-tree or QT, is computer science term that refers to a method of organizing data in four quadrants. Databases sometimes use quad trees to store and find their records. This type of organizational structure works especially well to find a particular bit or pixel in a two-dimensional image.
The quad tree somewhat follows the tree data structure commonly used in computer science. The normal tree data structure looks like an upside down tree, where a parent node at the top of the tree has one or more children nodes connected to it. Every other node on the tree has one parent node and can have any number of children nodes, including zero.
Unlike a normal tree data structure, a quad tree structure requires that each internal node have exactly four children nodes. When illustrating most quad tree structures, you'll see a node that has four children nodes hanging from it, with lines connecting the parent node with its children nodes. The illustration can continue, with four more children nodes hanging from each of the original four children nodes.
Other times, the illustration of a quad tree will be a region or square. Whenever the region reaches its maximum capacity for storing data, it is divided into four quadrants. Normally, the regions and the quadrants are squares, although they can be rectangles or other shapes, too.
A quad tree is a good data structure for organizing pixels in a photo and for organizing computer graphics. The picture can be divided into quadrants, and each quadrant can be divided into four more. This can be repeated again and again until you reach the level of individual pixels. If a quadrant contains pixels that are all the same color, however, there's no reason to further divide the quadrant.
Although data stored in a quad tree structure can require a lot of storage space compared to other methods of organizing data for computer graphics, the quad tree structure has several advantages. First, you can delete the entire photograph or graphic in a single step by clearing the root node, which clears all of its children nodes, too. Second, you quickly can reduce the resolution in a photograph by simply clearing the final level of children nodes. This will thereby reduce the amount of storage space it requires. Finally, finding a particular area of the photograph for image manipulation is easier with the quad tree structure.
Quad trees are used in a few other situations, too, including spatial indexing. Although quad trees are limited to two-dimensional images, representing a three-dimensional image can follow a similar structure, called an octree, which is the subdivision of a cube into eight children.
