Многомерное дерево отрезков — различия между версиями
Строка 1: | Строка 1: | ||
Дерево отрезков можно обобщить в многомерный случай. | Дерево отрезков можно обобщить в многомерный случай. | ||
− | Пусть задано <tex>p</tex>-мерное пространство с координатными осями <tex>x_1, x_2...x_p</tex>.Т.к. при построении одномерного дерева, индексы массива разбиваются на отрезки, тогда при построении многомерного дерева координаты будут обрабатываться сначала по <tex>x_1 </tex>, затем по <tex>x_2</tex> и т.д | + | Пусть задано <tex>p</tex>-мерное пространство с координатными осями <tex>x_1, x_2, x_3...x_p</tex>.Т.к. при построении одномерного дерева, индексы массива разбиваются на отрезки, тогда при построении многомерного дерева координаты будут обрабатываться сначала по <tex>x_1 </tex>, затем по <tex>x_2</tex> и т.д...Далее дерево строится рекурсивно: далее координаты по <tex>x_1</tex> обрабатываем по координатам <tex>x_2</tex>, <tex>x_3</tex> и т.д... |
Версия 01:13, 15 июня 2011
Дерево отрезков можно обобщить в многомерный случай.
Пусть задано
-мерное пространство с координатными осями .Т.к. при построении одномерного дерева, индексы массива разбиваются на отрезки, тогда при построении многомерного дерева координаты будут обрабатываться сначала по , затем по и т.д...Далее дерево строится рекурсивно: далее координаты по обрабатываем по координатам , и т.д...
Пример двумерного дерева
Анализ и оценка структуры
Структура использует
памяти, и отвечает на запрос за , где -размерность дерева.