Скачиваний:
20
Добавлен:
01.05.2014
Размер:
2.58 Mб
Скачать

Санкт-Петербургский государственный электротехнический

университет им. Ульянова В.И. (Ленина)

КАФЕДРА

МО ЭВМ

Лабораторная работа

по

дисциплине

Комбинаторные алгоритмы

Дерево отрезков”

Преподаватель: Ивановский С.А

Студенты гр.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 -> Генерировать отрезки

Вызывается диалоговое окно “ Генерировать отрезки ”

Задаем количество случайных отезков.Результат – в клиентской области окна (справа) отображается заданное число случайных отрезков.

7