Изменения
→Анализ и оценка структуры
Структура использует <tex>O(n^p)</tex> памяти, и отвечает на запрос за <tex>O(log^{p} n)</tex>, где <tex>p</tex>-размерность дерева.
Ответ на запрос в таком дереве будет производиться так же,как и построение: сначала по координате <tex>x_1</tex>, затем, когда дошли до какой-либо вершины по первой координате, вызвать запрос от этого же дерева по <tex>x_2</tex> и так далее.Получается, что для <tex>n-</tex>мерного дерева запрос выполняется за <tex>O(log (s_{x_1})* log (s_{x_2})...log (s_{x_n}))</tex> (для рассмотренного двумерного дерева будет <tex>log (n) * log (m) </tex> )
==Источники==
