Editing Interval tree (section)

===Higher dimensions===
{{Unreferenced section|date=November 2022}}

Augmented trees can be extended to higher dimensions by cycling through the dimensions at each level of the tree. For example, for two dimensions, the odd levels of the tree might contain ranges for the ''x''-coordinate, while the even levels contain ranges for the ''y''-coordinate. This approach effectively converts the data structure from an augmented binary tree to an augmented [[kd-tree]], thus significantly complicating the balancing algorithms for insertions and deletions.

A simpler solution is to use nested interval trees. First, create a tree using the ranges for the ''y''-coordinate. Now, for each node in the tree, add another interval tree on the ''x''-ranges, for all elements whose ''y''-range is the same as that node's ''y''-range.

The advantage of this solution is that it can be extended to an arbitrary number of dimensions using the same code base.

At first, the additional cost of the nested trees might seem prohibitive, but this is usually not so. As with the non-nested solution earlier, one node is needed per ''x''-coordinate, yielding the same number of nodes for both solutions. The only additional overhead is that of the nested tree structures, one per vertical interval. This structure is usually of negligible size, consisting only of a pointer to the root node, and possibly the number of nodes and the depth of the tree.