Editing Quadtree (section)

{{Short description|Tree data structure in which each internal node has exactly four children, to partition a 2D area}}
{{citation style|date=April 2015}}
{{Infobox data structure
| name               = Quadtree
| image              = 
| alt                = 
| caption            = 
| type               = Tree
| invented_by        = [[Raphael Finkel]] and [[J.L. Bentley]]
| invented_year      = 1974
| space_avg          = 
| space_worst        = 
| search_avg         = 
| search_worst       = 
| insert_avg         = 
| insert_worst       = 
| delete_avg         = 
| delete_worst       = 
| peek_avg           = 
| peek_worst         = 
| find_min_avg       = 
| find_min_worst     = 
| delete_min_avg     = 
| delete_min_worst   = 
| decrease_key_avg   = 
| decrease_key_worst = 
| merge_avg          = 
| merge_worst        = 
}}
[[Image:Point quadtree.svg|thumb|300px|A point-region quadtree with point data. Bucket capacity 1.]]
[[File:Quadtree compression of an image.gif|thumb|300x300px|Quadtree compression of an image step by step. Left shows the compressed image with the tree bounding boxes while the right shows just the compressed image]]
A '''quadtree''' is a [[tree data structure]] in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of [[octree]]s 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.<ref>{{cite journal |last1=Finkel |first1=R. A. |last2=Bentley |first2=J. L. |title=Quad trees a data structure for retrieval on composite keys |journal=Acta Informatica |date=1974 |volume=4 |issue=1 |pages=1–9 |doi=10.1007/BF00288933 |s2cid=33019699 |url=https://www.researchgate.net/publication/220197855 |access-date=6 November 2019}}</ref> 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 [[binary heap#Heap implementation|the way a complete binary tree can be stored compactly in an array]].<ref>
Milan Sonka, Vaclav Hlavac, Roger Boyle.
[https://books.google.com/books?id=DcETCgAAQBAJ "Image Processing, Analysis, and Machine Vision"].
2014.
p. 108-109.
</ref>