Многомерное дерево отрезков
Версия от 02:07, 15 июня 2011; 192.168.0.2 (обсуждение)
Дерево отрезков можно обобщить в многомерный случай.
Построение
Пусть задано
-мерное пространство с координатными осями .Т.к. при построении одномерного дерева, индексы массива разбиваются на отрезки, тогда при построении многомерного дерева координаты будут обрабатываться сначала по , затем по и так далее...Далее дерево строится рекурсивно: далее координаты по обрабатываем по координатам , ,то есть по всем возможным и далее по аналогии...То есть получается, что основная идея построения многомерного дерева отрезков - вкладывание деревьев отрезка друг в друга.Пример двумерного дерева
Анализ и оценка структуры
Структура использует
памяти, и отвечает на запрос за , где -размерность дерева.