Рандомизированные деревья

Тип работы:
Курсовая
Предмет:
Программирование
Страниц:
25

1430 Купить готовую работу
Узнать стоимость

Детальная информация о работе

Выдержка из работы

Однако, вероятность такого события даже при десятке тысяч узлов является маленькой.
Большим достоинством рандомизированного дерева, является тот факт, что мы очень легко можем сделать множественное удаление. Иногда бывает так, что для быстроты работы из дерева надо удалить целый список чисел. И лучше всего передать этот список процедуре удаления, чтобы она сделала всего один проход по дереву, удалив все вершины сразу. Обычно в балансируемом дереве этого сделать либо нельзя, либо нужно сильно усложнять процедуру удаления. Приходится удалять числа по одному, медленно и не красиво.
В рандомизированном дереве это сделать просто. А даже если бы это было не так, не обязательно строго следить за структурой веток. Поэтому мы можем не только сделать удаление за один вызов, мы можем просто выдрать из дерево любой количество произвольных вершин. Дерево само приведёт себя к рабочему состоянию.
Кроме того для рандомизированных деревьев, есть все операции, которые можно делать со множествами. Есть замечательные и простые алгоритмы: слияния, объединения, вычитания, пересечения и симметричной разности. Правда до состояния рабочего кода их надо немного доработать (на это пока не хватло времени).
Целью данной курсовой работы является реализация построения рандомизированного дерева на языке Object Pascal.
Задачи:
1. Постановка задачи
2. Описание алгоритма решения задачи
3. Реализация алгоритма на языке Object Pascal
4. Оценка сложности алгоритма

ПоказатьСвернуть

Содержание

Введение. 2

1. Описание и анализ поставленной задачи 4

1.1 Постановка задачи 4

1. 2 Описание структуры данных 4

2. Анализ методов решения задачи 5

2.1 Бинарное дерево поиска 5

2.2 Сбалансированные деревья поиска 6

2.3 Идеально-сбалансированное бинарное дерево 6

2.4 Сбалансированные АВЛ-деревья поиска 7

2.5 Рандомизированные деревья поиска 8

2.6 Операции над деревьями 8

3. Анализ и выбор структуры данных 9

3.1 Создание дерева. 10

3.2 Поиск (локализация) элемента в дереве. 10

3.3 Включение элемента в дерево. 11

3.4 Обработка данных в вершинах дерева. 12

3.5 Удаление элемента из бинарного дерева поиска. 13

3.6 Сохранение и восстановление дерева. 13

3.7 Уничтожение дерева. 14

4. Проектирование программного средства 14

4.1 Реализация структуры 15

4.2 Создание интерфейса программы. 20

5. Тестирование программы. 22

Заключение. 23

Список литературы. 24

Приложение. 25

Список литературы

1. Флёнов М. Е. «Delphi 2007. Секреты программирования.»

2. Стивене Р. «Delphi. Готовые алгоритмы»

3. Берж К. «Теория графов и ее приложения»

4. Уилсон Р. Введение в теорию графов. Пер с англ. М.: Мир, 1977

5. Роберт Седжвик, Алгоритмы на C++, М.: Вильямс, 2011 г.

Заполнить форму текущей работой