dimensions using an sort such as Heapsort or Mergesort prior to building the . Inserting a new point into a balanced k-d tree takes time. Removing a point from a balanced k-d tree takes time. Querying an axis-parallel range in a balanced k-d tree takes time, where m is the number of the reported points, and k the dimension of the k-d tree. Finding 1 nearest neighbour in a balanced k-d tree with randomly distributed points takes time on average. Variations Volumetric objects Instead of points, a k-d tree can also contain rectangles or hyperrectangles. Thus range search becomes the problem of returning all rectangles intersecting the search rectangle. The tree is constructed the usual way with all the rectangles at the leaves. In an orthogonal range search, the opposite coordinate is used when comparing against the median. For example, if the current level is split along xhigh, we check the xlow coordinate of the search rectangle. If the median is less than the xlow coordinate of the search rectangle, then no rectangle in the left branch can ever intersect with the search rectangle and so can be pruned. Otherwise both branches should be traversed. See also interval tree, which is a 1-dimensional special case. Points only in leaves It is also possible to define a k-d tree with points stored solely in leaves. This form of k-d tree allows a variety of split mechanics other than the standard median split. The midpoint splitting rule selects on the middle of the longest axis of the space being searched, regardless of the distribution of points. This guarantees that the aspect ratio will be at most 2:1, but the depth is dependent on the distribution of points. A variation, called sliding-midpoint, only splits on the middle if there are points on both sides of the split. Otherwise, it splits on point nearest to the middle. Maneewongvatana and Mount show that this offers "good enough" performance on common data sets. Using sliding-midpoint, an approximate nearest neighbour query can be answered in . Approximate range counting can be answered in with this method. See also Close variations: implicit k-d tree, a k-d tree defined by an implicit splitting function rather than an explicitly-stored set of splits min/max k-d tree, a k-d tree that associates a minimum and maximum value with each of its nodes Relaxed k-d tree, a k-d tree such that the discriminants