Многомерное дерево отрезков — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
  
 
==Пример двумерного дерева==
 
==Пример двумерного дерева==
 
+
Рассмотрим процесс построения предельного случая при <tex>p = 2</tex>.
 +
Пусть задан массив элементов  размера <tex>n \times m</tex>.Упорядочим массив по первой координате и построим на нем дерево отрезков.После этого для каждого узла дерева строим еще одно дерево отрезков по координате <tex>y</tex>, которые находятся на том же отрезке.
  
 
==Анализ и оценка структуры==
 
==Анализ и оценка структуры==
 
Структура использует <tex>O(n^p</tex>  памяти, и отвечает на запрос за <tex>O(log^{p} n)</tex>, где <tex>p</tex>-размерность дерева.
 
Структура использует <tex>O(n^p</tex>  памяти, и отвечает на запрос за <tex>O(log^{p} n)</tex>, где <tex>p</tex>-размерность дерева.

Версия 06:02, 15 июня 2011

Дерево отрезков можно обобщить в многомерный случай.

Построение

Пусть задано [math]p[/math]-мерное пространство с координатными осями [math]x_1, x_2, x_3...x_p[/math].Т.к. при построении одномерного дерева, индексы массива разбиваются на отрезки, тогда при построении многомерного дерева координаты будут обрабатываться сначала по [math]x_1 [/math], затем по [math]x_2[/math] и так далее...Далее дерево строится рекурсивно: далее координаты по [math]x_1[/math] обрабатываем по координатам [math]x_2[/math], [math]x_3[/math],то есть по всем возможным и далее по аналогии...То есть получается, что основная идея построения многомерного дерева отрезков - вкладывание деревьев отрезка друг в друга.

Пример двумерного дерева

Рассмотрим процесс построения предельного случая при [math]p = 2[/math]. Пусть задан массив элементов размера [math]n \times m[/math].Упорядочим массив по первой координате и построим на нем дерево отрезков.После этого для каждого узла дерева строим еще одно дерево отрезков по координате [math]y[/math], которые находятся на том же отрезке.

Анализ и оценка структуры

Структура использует [math]O(n^p[/math] памяти, и отвечает на запрос за [math]O(log^{p} n)[/math], где [math]p[/math]-размерность дерева.