Дерево - интервал
Cтраница 1
Дерево интервалов по своей форме напоминает пирамиду, и обычно о нем говорят как о дереве деревьев. Мы начнем со структуры для одномерного случая, а затем рекурсивно определим деревья для случая d - мерных пространств, основываясь при этом на ( d - 1) - мерном случае. Дерево интервалов для двумерного случая - это обычное сбалансированное дерево бинарного поиска, организованное в соответствии со второй координатой каждой записи. Каждому листу дерева соответствует одна запись, а каждому узлу - записи в его поддереве. Кроме того, к каждому узлу присоединено одномерное дерево интервалов, организующее записи, соответствующие узлу, в зависимости от их первой координаты. Отсюда видно, что п записей на уровне i примерно равномерно распределены между 2 узлами. Это распределение распространяется примерно на Iog2 n уровней и подходящим образом заканчивается, когда множество записей становится настолько маленьким, что все они могут быть без затруднений просмотрены методом грубой силы. Эта же идея обобщается на случай пространств более высокой размерности, так что в случае d - мерного пространства мы имеем сбалансированное дерево бинарного поиска по координате с номером d, а каждый узел связан с ( d - 1) - мерным деревом интервалов для ( d - 1) - мерных записей, соответствующих узлу. [1]
Дерево интервалов по своей форме напоминает пирамиду, и обычно о нем говорят как о дереве деревьев. Мы начнем со структуры для одномерного случая, а затем рекурсивно определим деревья для случая d - мерных пространств, основываясь при этом на ( d - 1) - мерном случае. Дерево интервалов для двумерного случая - это обычное сбалансированное дерево бинарного поиска, организованное в соответствии со второй координатой каждой записи. Каждому листу дерева соответствует одна запись, а каждому узлу - записи в его поддереве. Кроме того, к каждому узлу присоединено одномерное дерево интервалов, организующее записи, соответствующие узлу, в зависимости от их первой координаты. Отсюда видно, что n записей на уровне i примерно равномерно распределены между 2 узлами. Это распределение распространяется примерно на Iog2 n уровней и подходящим образом заканчивается, когда множество записей становится настолько маленьким, что все они могут быть без затруднений просмотрены методом грубой силы. Эта же идея обобщается на случай пространств более высокой размерности, так что в случае d - мерного пространства мы имеем сбалансированное дерево бинарного поиска по координате с номером а, а каждый узел связан с ( d - 1) - мерным деревом интервалов для ( d - 1) - мерных записей, соответствующих узлу. [2]
На рис. 8.30 приведен пример отнесения интервалов в статическом дереве интервалов. [4]
Во-первых, рассмотрим вопрос об управлении вставками и удалениями в статическом дереве интервалов. Проверка того, что при этом левые и правые указатели можно поддерживать за константное время в расчете на один узел, является достаточно простым упражнением. [6]
Превосходное решение было получено в результате введения [ McCreight ( 1981); Edelsbrunner ( 1980) ] новой структуры данных, названной Эдельсбруннером деревом интервалов. Хотя возможна и более совершенная динамическая версия интервального дерева, мы ограничимся простым статическим вариантом, пригодным для наших целей. [7]
Анализ трудоемкости вышеописанного метода не составляет труда. Прежде всего статическое дерево интервалов для набора из N интервалов требует 0 ( N) памяти, поскольку в нем будет 4N - 1 первичных узлов, и еще не более 2N элементов необходимо запомнить во вторичных списках. Скелетная первичная структура строится за время 0 ( N ogN), поскольку необходима предварительная сортировка абсцисс. Каждый интервал вставляется или удаляется за время 0 ( ogN), как упоминалось выше. Поиск в дереве требует 0 ( ogN) времени для прослеживания поисковых путей ( см. опять рис. 8.31), хотя на каждый обнаруженный интервал тратится константное время; единственные накладные расходы, относящиеся к соответствующему первичному узлу, пропорциональны числу вторичных списков, обрабатываемых в процессе данной работы. [8]
Структура дерева интервалов будет описана ниже. [9]
Структура дерева интервалов бу - дет описана ниже. [10]
Дерево интервалов по своей форме напоминает пирамиду, и обычно о нем говорят как о дереве деревьев. Мы начнем со структуры для одномерного случая, а затем рекурсивно определим деревья для случая d - мерных пространств, основываясь при этом на ( d - 1) - мерном случае. Дерево интервалов для двумерного случая - это обычное сбалансированное дерево бинарного поиска, организованное в соответствии со второй координатой каждой записи. Каждому листу дерева соответствует одна запись, а каждому узлу - записи в его поддереве. Кроме того, к каждому узлу присоединено одномерное дерево интервалов, организующее записи, соответствующие узлу, в зависимости от их первой координаты. Отсюда видно, что п записей на уровне i примерно равномерно распределены между 2 узлами. Это распределение распространяется примерно на Iog2 n уровней и подходящим образом заканчивается, когда множество записей становится настолько маленьким, что все они могут быть без затруднений просмотрены методом грубой силы. Эта же идея обобщается на случай пространств более высокой размерности, так что в случае d - мерного пространства мы имеем сбалансированное дерево бинарного поиска по координате с номером d, а каждый узел связан с ( d - 1) - мерным деревом интервалов для ( d - 1) - мерных записей, соответствующих узлу. [11]
Дерево интервалов по своей форме напоминает пирамиду, и обычно о нем говорят как о дереве деревьев. Мы начнем со структуры для одномерного случая, а затем рекурсивно определим деревья для случая d - мерных пространств, основываясь при этом на ( d - 1) - мерном случае. Дерево интервалов для двумерного случая - это обычное сбалансированное дерево бинарного поиска, организованное в соответствии со второй координатой каждой записи. Каждому листу дерева соответствует одна запись, а каждому узлу - записи в его поддереве. Кроме того, к каждому узлу присоединено одномерное дерево интервалов, организующее записи, соответствующие узлу, в зависимости от их первой координаты. Отсюда видно, что n записей на уровне i примерно равномерно распределены между 2 узлами. Это распределение распространяется примерно на Iog2 n уровней и подходящим образом заканчивается, когда множество записей становится настолько маленьким, что все они могут быть без затруднений просмотрены методом грубой силы. Эта же идея обобщается на случай пространств более высокой размерности, так что в случае d - мерного пространства мы имеем сбалансированное дерево бинарного поиска по координате с номером а, а каждый узел связан с ( d - 1) - мерным деревом интервалов для ( d - 1) - мерных записей, соответствующих узлу. [12]
Дерево интервалов по своей форме напоминает пирамиду, и обычно о нем говорят как о дереве деревьев. Мы начнем со структуры для одномерного случая, а затем рекурсивно определим деревья для случая d - мерных пространств, основываясь при этом на ( d - 1) - мерном случае. Дерево интервалов для двумерного случая - это обычное сбалансированное дерево бинарного поиска, организованное в соответствии со второй координатой каждой записи. Каждому листу дерева соответствует одна запись, а каждому узлу - записи в его поддереве. Кроме того, к каждому узлу присоединено одномерное дерево интервалов, организующее записи, соответствующие узлу, в зависимости от их первой координаты. Отсюда видно, что п записей на уровне i примерно равномерно распределены между 2 узлами. Это распределение распространяется примерно на Iog2 n уровней и подходящим образом заканчивается, когда множество записей становится настолько маленьким, что все они могут быть без затруднений просмотрены методом грубой силы. Эта же идея обобщается на случай пространств более высокой размерности, так что в случае d - мерного пространства мы имеем сбалансированное дерево бинарного поиска по координате с номером d, а каждый узел связан с ( d - 1) - мерным деревом интервалов для ( d - 1) - мерных записей, соответствующих узлу. [13]
Дерево интервалов по своей форме напоминает пирамиду, и обычно о нем говорят как о дереве деревьев. Мы начнем со структуры для одномерного случая, а затем рекурсивно определим деревья для случая d - мерных пространств, основываясь при этом на ( d - 1) - мерном случае. Дерево интервалов для двумерного случая - это обычное сбалансированное дерево бинарного поиска, организованное в соответствии со второй координатой каждой записи. Каждому листу дерева соответствует одна запись, а каждому узлу - записи в его поддереве. Кроме того, к каждому узлу присоединено одномерное дерево интервалов, организующее записи, соответствующие узлу, в зависимости от их первой координаты. Отсюда видно, что n записей на уровне i примерно равномерно распределены между 2 узлами. Это распределение распространяется примерно на Iog2 n уровней и подходящим образом заканчивается, когда множество записей становится настолько маленьким, что все они могут быть без затруднений просмотрены методом грубой силы. Эта же идея обобщается на случай пространств более высокой размерности, так что в случае d - мерного пространства мы имеем сбалансированное дерево бинарного поиска по координате с номером а, а каждый узел связан с ( d - 1) - мерным деревом интервалов для ( d - 1) - мерных записей, соответствующих узлу. [14]
Каждый узел в дереве представляет некоторый интервал по ( / - координате. При прохождении узла мы прежде всего сравниваем ( / - интервал запроса с ( / - интервалом узла. Если / - интервал узла целиком попадает в ( / - интервал запроса, то мы осуществляем поиск в упорядоченном массиве, запоминаемом в узле, для обнаружения всех точек, попадающих в х-интервал запроса. Если ( / - интервал запроса целиком находится ниже величины, с которой производится сравнение в узле, то мы рекурсивно проходим левое поддерево. Если ( / - интервал запроса целиком находится выше величины, с которой производится сравнение в узле, то мы рекурсивно проходим правое поддерево. В противном случае ( ( / - интервал запроса содержит величину, с которой производится сравнение) мы проходим оба поддерева. Анализ планарного дерева интервалов довольно сложен. Что касается времени ответа, то анализ показывает, что на каждом уровне дерева производится поиск не более чем в двух упорядоченных массивах, на что в каждом случае тратится время 0 ( log), поэтому суммарные затраты составляют О ( log2) плюс время на выборку ответа. [15]
Страницы: 1 2