Региональный поиск дерево отрезков / doc / doc
.Санкт-Петербургский государственный электротехнический
университет им. Ульянова В.И. (Ленина)
КАФЕДРА
МО ЭВМ
Лабораторная работа
по
дисциплине
Комбинаторные алгоритмы
“Дерево отрезков”
Преподаватель: Ивановский С.А
Студенты гр.8341: Шинкевич И.
Мурашова И.
2003
1.Задание.
Заданы интервалы на числовой оси, концы которых принадлежат фиксированному множеству из N точек. Представить множество интервалов деревом отрезков.
2.Теоретические материалы.
Дерево отрезков, впервые введенное Дж. Бентли (Bentley (1997)), это структура данных, созданная для работы с интервалами на числовой оси, концы которых принадлежат фиксированному множеству из N абсцисс. Поскольку множество абсцисс фиксировано, то дерево отрезков представляет собой статическую структуру, на которой не разрешены вставки и удаления абсцисс. Абсциссы нормализуют, заменяя их порядковыми номерами (при обходе слева направо). Таким образом, можно считать эти абсциссы целыми числами в интервале [1,N].
Дерево отрезков – это двоичное дерево с корнем. Для заданных целых чисел l и r таких, что l<r дерево отрезков T(l,r) строится рекурсивно следующим образом: оно состоит из корня v с параметрами B[v]=l, E[v]=r, а если еще r-l>1, то оно состоит из левого поддерева T(l,(B[v]+E[v])/2) и правого поддерева T((B[v]+E[v])/2,r). Корни этих поддеревьев естественно обозначать через ЛевыйСын[v] и ПравыйСын[v] соответственно. Параметры B[v] и E[v] обозначают интервал [B[v],E[v]] из [l,r], связанный с узлом v (Рис 1.)
Рис. 1. Пример дерева отрезков
Интервалы, принадлежащие множеству {[B[v],E[v]]: v-узел T(l,r)}, называются стандартными интервалами дерева T(l,r). Стандартные интервалы, принадлежащие листьям T(l,r), называются элементарными интервалами. Легко показать, что дерево отрезков T(l,r) сбалансировано и имеет глубину log 2 (r-l).
Действительно, в каждом узле происходит разбиение интервала [B[v],E[v]] ровно (?) в центре, что приводит к тому, что глубина левого и правого поддеревьев будет всегда одинаковой, за исключением того случая, когда длина интервала равна трем (?). В любом случае, все листья окажутся на последних двух уровнях, что говорит о сбалансированности дерева. Определение глубины естественным образом следует из сбалансированности и бинарности дерева отрезков.
Дерево отрезков T(l,r) предназначено для динамического запоминания тех интервалов, чьи концы принадлежат множеству {l,l+1,…,r} (т.е. допустимы операции вставки и удаления). В частности, при r-l>3 произвольный интервал [b,e] с целыми b<e будет разбит в набор из не более, чем log 2 (r-l)+log 2(r-l)-2 стандартных интервалов дерева T(l,r).
Данное утверждение легко доказать, заметив тот факт, что в разбиение интервала [b,e] не могут одновременно входить ЛевыйСын и ПравыйСын одного узла, поскольку в этом случае будет использован сам узел, в то же время, если в разбиение входит определенный узел, то его потомки не входят в разбиение. Также не может быть ситуации, когда в разбиение входят узлы [n,k], [p,t], p>k, но не входит узел [k,p]. Таким образом, на каждом уровне дерева отрезков могут находиться только один или два узла, относящиеся к разбиению отрезка [b,e].
Рис. 2. Вставка интервала [2,5] в T(1,7)
Начальный путь Pнач (возможно пустой) от корня до v*, называемого развилкой (в примере Pнач-пустой, v*=[1,7]), из которого выходят два пути Pл, Pп (возможно пустые). Вставляемый интервал относится или полностью к развилке (Pп,Pл-пустые) или ко всем правым сыновьям Pл, которые сами не на Pл и ко всем левым сыновьям Pп, которые сами не на Pп; фрагментация определяется узлами отнесения (выделены рамкой). Все свойства пути легко выводятся из рассуждений о количестве интервалов разбиения.
3.Алгоритм.
1)для построения интервалов на числовой оси размещаются N точек
2)формируется дерево для отображения интервалов
3)ввод отрезка
4)поиск и отображение отрезка в дереве.
Алгоритм поиска в дереве отрезков выглядит следующим образом:
Procedure ВСТАВИТЬ(b,e,v)
Begin
If (b<=B[v]) And (E[v]<=e) Then назначить [b,e] узлу v
Else Begin
If (b<(B[v]+E[v])/2) Then ВСТАВИТЬ (b,e,ЛевыйСын[v])
If ((B[v]+E[v])/2<e) Then ВСТАВИТЬ (b,e,ПравыйСын[v])
End
End.
4. Пример работы алгоритма.
Отображение заданного интервала в дереве отрезков.
5. Описание программы
-
Функции
- построение дерева отрезков
-
ввод отрезка (или генерация набора отрезков случайным образом)
-
удаление заданного отрезка
-
представление заданного отрезка в дереве
-
Интерфейс
Программа имеет стандартный GUI – интерфейс для операционной системы Windows.
Клиентская область окна делится на две части , в одной графически отображаются интервалы на числовой оси ,а в другой дерево отрезков.
Меню включает в себя пункты :
-
File
-
Help
-
View
-
Tools
Пункт меню “File”:
Подменю содержит следующие пункты :
-
New
-
Save
-
Open
-
Exit
Подменю “New” ... “Open ” представляют собой стандартное меню работы с файлами данных программы. Представлены стандартные операции по созданию, сохранению и загрузке файлов.
Пункт меню “Help” предоставляет сведения о программе.
Пункт меню “Tools” позволяет пользователю работать с данными программы.
Подменю содержит следующие пункты:
-
Количество точек
-
Добавить отрезок
-
Удалить отрезок
-
Показать отрезок
-
Генерировать отрезки
Подменю “Количество точек ” : ввод пользователем N (количесва точек на числовой прямой) и
Отображение их в клиентской области (в правой её части) на числовой оси.
“Добавить отрезок“ - ввод пользователем нового отрезка и отображение его в клиентской области окна (в правой части) .
“Генерировать отрезки“ - ввод пользователем количества отрезков, генерация заданного числа отрезков случайным образом и отображение их в клиентской области окна (в правой части) .
“Показать отрезок” – выделение цветом отрезка в правой части клиентской области и выделение
цветом узлов дерева отрезков, cответствующих заданному отрезку, в левой части клиентской области окна.
“Удалить отрезок ” – ввод пользователем координат отрезка и удаление его из клиентской области окна (в правой части) .
( Пункты “ Добавить отрезок ”,”Генерировать отрезки”,” Показать отрезок ”,” Удалить отрезок ” доступны только после пвыполнения пункта “Количество точек ”. Пункты ”Показать отрезок ”,” Удалить отрезок ” доступны только после пвыполнения пункта “Добавить отрезок ” или “Генерировать отрезки”.)
6. Пример работы программы.
Представление интервала [2,4] , заданного на числовой оси (четыре точки) , в дереве отрезков .
Запуск программы KURSOVIK.EXE
Tools -> Количество точек
Вызывается диалоговое окно “ Количество точек ”
Задаем N (четыре точки)
Tools -> Добавить отрезок
Вызывается диалоговое окно “ Добавить отрезок ”
Задаем координаты отрезка ( [2,4] )
Tools -> Показать отрезок
Вызывается диалоговое окно “ Показать отрезок ”
З адаем координаты отрезка ( [2,4] )
Отображение интервала в дереве отрезков:
Пункт меню Tools -> Генерировать отрезки
Вызывается диалоговое окно “ Генерировать отрезки ”
Задаем количество случайных отезков.Результат – в клиентской области окна (справа) отображается заданное число случайных отрезков.