“Деревья двоичного поиска”, операциями над последовательностями: сцепление(CONCAT), исключение(EXCL), замена (CHANGE)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования

«Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»

им. В.И.Ульянова(Ленина)»

Отчет по лабораторной работе №3

по дисциплине «Алгоритмы и структуры данных»

Вариант №14

Выполнили студенты группы 5308:

Яковлева Наталья Сергеевна

Васильев Никита Олегович

Проверил преподаватель:

Колинько Павел Георгиевич

Санкт-Петербург

2017

Задание к лабораторной работе

Дополнить программу, составленную по теме “Деревья двоичного поиска”, операциями над последовательностями: сцепление(CONCAT), исключение(EXCL), замена (CHANGE).

Выбрать такой способ доработки структуры данных, чтобы получились эффективные алгоритмы.

Вид дерева: АВЛ-дерево (с автобалансировкой).

Оценка временной сложности алгоритма

Вставка с балансировкой:

Временная сложность - О(log(n)), где n-мощность множества.

Операция проверки принадлежности элемента множеству:

Временная сложность - О(log(n)).

Двуместные операции:

Временная сложность - О(n*log(n)).

Операция сцепления:

Временная сложность - О(n).

Операция исключения:

Временная сложность O(n+m), n- размерность первого множества, m - размерность второго множества.

Операция замены:

Временная сложность O(n+m), n- размерность первого множества, m - размерность второго множества.

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

В нашей программе был выбран подход, в котором для каждого узла формируется список для хранения порядковых номеров данного ключа в последовательности.

Данный способ не вызывает никаких проблем при вставке новых ключей или поиске номера по значению. Для удаления ключа или поиска ключа по порядковому номеру требуется просмотр всей структуры данных для корректировки номеров. Стоит отметить, что данный способ не вызывает проблем с реализацией, т.к. является простым и понятным.

Примеры работы программы

Пример 1.

Множество А:

Множество В:

Исключение:

Замена:

Сцепление:

Вывод

В ходе лабораторной работы мы научились преобразовывать АВЛ-деревья для работы с множествами в деревья для работы с последовательностями и реализовывать различные операции над ними.

Использованная литература

1. Т. Кормен “Алгоритмы. Построение и анализ”, издательский дом “Вильямс”, 2013г.

2. Н.Вирт “Алгоритмы и структуры данных”, издательство “Мир”, 1989г.

...