Прочитал вот эту статью:
goo.gl/kXmR7L и соответствующие главы из де Берга, Computational Geometry. В качестве основы дерева предлагается "использовать сбалансированное бинарное дерево поиска, в листьях которого будем хранить точки искомого множества, а в нелистовых вершинах - разделющие значения, по которым будет вестись поиск в дереве."
Одномерное range-tree — просто дерево поиска, описанное выше.
d-мерное range-tree — дерево поиска (по первой координате X_1), аналогичное описанному выше, но в каждой вершине дополнительно хранящее d-1-мерное range-tree (по остальным координатам X_2 x ... x X_d) для множества элементов, являющихся листами поддерева этой вершины.
Предположим, надо построить дерево из таких точек: (1, 2), (1, 3) и (1, 4). Очевидно, невозможно сделать такое дерево поиска, чтобы у него было несколько одинаковых листов. Ну вот как тогда построить дерево поиска из первых x-координат, то есть из единиц?) Что за тип данных такой, который не может хранить даже такой простой пример?) Где я неверно понял определение?
Средний
