Operations on k-d trees

Construction. Since there are many possible ways to choose axis-aligned splitting planes, there are many different ways to construct k-d trees.

• As one moves down the tree, one cycles through the axes used to select the splitting planes. For example, in a 3-dimensional tree, the root would have an $x$-aligned plane, the root's children would both have $y$-aligned planes, the root's grandchildren would all have $z$-aligned planes, the root's great-grandchildren would all have $x$-aligned planes, the root's great-great-grandchildren would all have $y$-aligned planes, and so on.)
• Points are inserted by selecting the median of the points being put into the subtree, with respect to their coordinates in the axis being used to create the splitting plane. (Note the assumption that we feed the entire set of n points into the algorithm up-front.)

Adding elements, Removing elements, Balancing, Nearest neighbour search, are the other operations.