Editing Octree (section)

{{Short description|Tree data structure in which each internal node has exactly eight children, to partition a 3D space}}
{{Infobox data structure
| name               = Octree
| image              = 
| alt                = 
| caption            = 
| type               = Tree
| invented_by        = Donald Meagher
| invented_year      = 1980
| space_avg          = O(N)
| space_worst        = O(N)
| search_avg         = O(logN+K)
| search_worst       = O(logN+K)
| insert_avg         = O(logN)
| insert_worst       = O(logN)
| delete_avg         = O(logN)
| delete_worst       = O(logN)
| peek_avg           = O(logN)
| peek_worst         = O(logN)
| find_min_avg       = 
| find_min_worst     = 
| delete_min_avg     = 
| delete_min_worst   = 
| decrease_key_avg   = 
| decrease_key_worst = 
| merge_avg          = 
| merge_worst        = 
}}
[[File:Octree2.svg|thumb|Left: Recursive subdivision of a cube into [[octant (solid geometry)|octant]]s. Right: The corresponding octree.]]

An '''octree''' is a [[tree data structure]] in which each [[internal node]] has exactly eight [[child node|children]]. Octrees are most often used to partition a [[three-dimensional space]] by [[recursive subdivision|recursively subdividing]] it into eight [[Octant (geometry)|octants]]. Octrees are the three-dimensional analog of [[quadtree]]s. The word is derived from ''oct'' (Greek root meaning "eight") + ''tree''. Octrees are often used in [[3D graphics]] and 3D [[game engine]]s.