Cтраница 2
Каждый узел в дереве представляет некоторый интервал по ( / - координате. При прохождении узла мы прежде всего сравниваем ( / - интервал запроса с ( / - интервалом узла. Если / - интервал узла целиком попадает в ( / - интервал запроса, то мы осуществляем поиск в упорядоченном массиве, запоминаемом в узле, для обнаружения всех точек, попадающих в х-интервал запроса. Если ( / - интервал запроса целиком находится ниже величины, с которой производится сравнение в узле, то мы рекурсивно проходим левое поддерево. Если ( / - интервал запроса целиком находится выше величины, с которой производится сравнение в узле, то мы рекурсивно проходим правое поддерево. В противном случае ( ( / - интервал запроса содержит величину, с которой производится сравнение) мы проходим оба поддерева. Анализ планарного дерева интервалов довольно сложен. Что касается времени ответа, то анализ показывает, что на каждом уровне дерева производится поиск не более чем в двух упорядоченных массивах, на что в каждом случае тратится время 0 ( log), поэтому суммарные затраты составляют 0 ( log2) плюс время на выборку ответа. [16]
Дерево интервалов по своей форме напоминает пирамиду, и обычно о нем говорят как о дереве деревьев. Мы начнем со структуры для одномерного случая, а затем рекурсивно определим деревья для случая d - мерных пространств, основываясь при этом на ( d - 1) - мерном случае. Дерево интервалов для двумерного случая - это обычное сбалансированное дерево бинарного поиска, организованное в соответствии со второй координатой каждой записи. Каждому листу дерева соответствует одна запись, а каждому узлу - записи в его поддереве. Кроме того, к каждому узлу присоединено одномерное дерево интервалов, организующее записи, соответствующие узлу, в зависимости от их первой координаты. Отсюда видно, что n записей на уровне i примерно равномерно распределены между 2 узлами. Это распределение распространяется примерно на Iog2 n уровней и подходящим образом заканчивается, когда множество записей становится настолько маленьким, что все они могут быть без затруднений просмотрены методом грубой силы. Эта же идея обобщается на случай пространств более высокой размерности, так что в случае d - мерного пространства мы имеем сбалансированное дерево бинарного поиска по координате с номером а, а каждый узел связан с ( d - 1) - мерным деревом интервалов для ( d - 1) - мерных записей, соответствующих узлу. [17]
Дерево интервалов по своей форме напоминает пирамиду, и обычно о нем говорят как о дереве деревьев. Мы начнем со структуры для одномерного случая, а затем рекурсивно определим деревья для случая d - мерных пространств, основываясь при этом на ( d - 1) - мерном случае. Дерево интервалов для двумерного случая - это обычное сбалансированное дерево бинарного поиска, организованное в соответствии со второй координатой каждой записи. Каждому листу дерева соответствует одна запись, а каждому узлу - записи в его поддереве. Кроме того, к каждому узлу присоединено одномерное дерево интервалов, организующее записи, соответствующие узлу, в зависимости от их первой координаты. Отсюда видно, что п записей на уровне i примерно равномерно распределены между 2 узлами. Это распределение распространяется примерно на Iog2 n уровней и подходящим образом заканчивается, когда множество записей становится настолько маленьким, что все они могут быть без затруднений просмотрены методом грубой силы. Эта же идея обобщается на случай пространств более высокой размерности, так что в случае d - мерного пространства мы имеем сбалансированное дерево бинарного поиска по координате с номером d, а каждый узел связан с ( d - 1) - мерным деревом интервалов для ( d - 1) - мерных записей, соответствующих узлу. [18]