Editing Quadtree (section)

===Point quadtree===
The point quadtree<ref>{{Cite journal|last1=Finkel|first1=R. A.|last2=Bentley|first2=J. L.|year=1974|title=Quad Trees A Data Structure for Retrieval on Composite Keys|journal=Acta Informatica|publisher=Springer-Verlag|volume=4|pages=1–9|doi=10.1007/bf00288933|s2cid=33019699}}</ref> is an adaptation of a [[binary tree]] used to represent two-dimensional point data. It shares the features of all quadtrees but is a true tree as the center of a subdivision is always on a point. It is often very efficient in comparing two-dimensional, ordered data points, usually operating in [[Big O notation|O(log n)]] time. Point quadtrees are worth mentioning for completeness, but they have been surpassed by [[k-d tree|''k''-d trees]] as tools for generalized binary search.<ref name=Aluru2004>{{Cite book|title=Handbook of Data Structures and Applications|last=Aluru|first=S.|publisher=Chapman and Hall/CRC|year=2004|isbn=9781584884354|editor-last=D. Mehta and S. Sahni|pages=19-1 -- 19-26|chapter=Quadtrees and octrees}}</ref>

Point quadtrees are constructed as follows. Given the next point to insert, we find the cell in which it lies and add it to the tree. The new point is added such that the cell that contains it is divided into quadrants by the vertical and horizontal lines that run through the point. Consequently, cells are rectangular but not necessarily square. In these trees, each node contains one of the input points.

Since the division of the plane is decided by the order of point-insertion, the tree's height is sensitive to and dependent on insertion order. Inserting in a "bad" order can lead to a tree of height linear in the number of input points (at which point it becomes a linked-list). If the point-set is static, pre-processing can be done to create a tree of balanced height.

====Node structure for a point quadtree====
A node of a point quadtree is similar to a node of a [[binary tree]], with the major difference being that it has four pointers (one for each quadrant) instead of two ("left" and "right") as in an ordinary binary tree. Also a key is usually decomposed into two parts, referring to x and y coordinates. Therefore, a node contains the following information:
* four pointers: quad[‘NW’], quad[‘NE’], quad[‘SW’], and quad[‘SE’]
* point; which in turn contains:
** key; usually expressed as x, y coordinates
** value; for example a name