Порядок выполнения лабораторной работы

Работа предполагает выполнение следующих этапов.

1. Знакомство со всеми разделами руководства.

2. Получение у преподавателя задания на разработку программы для алгоритмов сортировки (см. Приложение 4).

3. Разработка и отладка заданных программ.

4. Получение верхней и экспериментальной оценки времени выполнения заданных алгоритмов и программ.

5. Нахождение предельной оценки емкости памяти, необходимой для выполнения разработанных программ.

Содержание отчета о выполненной работе

Отчет о выполненной работе должен содержать.

1. Название и цель работы.

2. Словесное описание заданных алгоритмов сортировки.

3. Тексты программ.

4. Формулы верхней оценки временной и емкостной сложности заданных алгоритмов.

5. Результаты экспериментальной оценки временной и емкостной сложности заданных алгоритмов.

Контрольные вопросы

1. Что такое сортировка и для чего она нужна?

2. По каким признакам выполняется классификация алгоритмов сортировки?

3. Как оценивается временная сложность алгоритмов упорядочения?

4. Как оценивается емкостная сложность алгоритмов сортировки?

5. Какой метод упорядочения самый простой?

6. Какой алгоритм сортировки самый быстрый?

7. Какие алгоритмы пригодны для упорядочения файлов?

8. Чем отличается сортировка чисел от строк?

9. Как Вы определили время выполнения Ваших алгоритмов?

10. Как Вы определили объем памяти, необходимой для выполнения Ваших алгоритмов?

11. Каковы основные отличия сортировки вставками от «пузырьковой»?

12. Каковы основные отличия упорядочения слиянием от «пузырьковой»?

13. Каковы основные отличия сортировки слиянием от метода Боуза-Нельсона?

14. Каковы основные отличия упорядочения слиянием и вставками?

15. Каковы отличительные особенности быстрой сортировки?

16. Как выполняется упорядочение Шейкером?

17. Каковы особенности сортировки Шелла и для каких данных она предпочтительна?

18. У каких известных Вам методов сортировки временная сложность зависит от объема используемой памяти?

Лабораторная работа №5 исследование и оценка алгоритмов поиска на деревьях Краткая теория

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

Двоичные и В+ деревья. Основные понятия и определения

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

Древовидная структура содержит множество узлов (nodes), происходящих от единственного начального, который называют корнем (root). На Рис. 5.1 корнем является узел А. Принято узел считать родителем (parent), указывающим на 0, 1 или более других узлов, называемых сыновьями (children). Например, узел В является родителем сыновей E и F. Дерево может представлять несколько поколений. Сыновья узла и сыновья их сыновей называются потомками (descendants), а родители и прародители – предками (ancestors) этого узла. Например, узлы E, F, I, J – потомки узла B. Каждый некорневой узел имеет только одного родителя, и каждый родитель имеет 0 или более сыновей. Узел, не имеющий детей (E, G, H, I, J), называется листом (leaf).

Каждый узел дерева является корнем поддерева (subtree), которое включает в себя этот узел и всех его потомков. Так, F есть корень поддерева, содержащего узлы F, I и J. Узел G является корнем поддерева без потомков. Таким образом, узел A есть корень поддерева, которое само оказывается деревом.

Рис. 5.1. Графическое изображение дерева

Каждый узел дерева является корнем поддерева (subtree), которое включает в себя этот узел и всех его потомков. Так, F есть корень поддерева, содержащего узлы F, I и J. Узел G является корнем поддерева без потомков. Таким образом, узел A есть корень поддерева, которое само оказывается деревом.

Переход от родительского узла к дочернему и другим потомкам осуществляется вдоль пути (path). Например, на рисунке 5.2 путь от корня A к узлу F проходит от A к B и от B к F. Тот факт, что каждый некорневой узел имеет единственного родителя, гарантирует, что существует единственный путь из любого узла к его потомкам. Длина пути от корня к этому узлу есть уровень узла. Уровень корня равен 0. Каждый сын корня является узлом 1-го уровня, следующее поколение – узлами 2-го уровня и т.д. Например, на рисунке 5.2 узел F является узлом 2-го уровня с длиной пути 2.

Рис. 5.2. Уровень узла и длина пути

Глубина (depth) дерева есть его максимальный уровень. Понятие глубины также может быть описано в терминах пути. Глубина дерева есть длина самого длинного пути от корня до узла. На рис. 5.2 глубина дерева равна 3.

В программировании широкое распространение получили так называемые двоичные (бинарные - binary trees) деревья, которые имеют унифицированную структуру, обеспечивающую разнообразные алгоритмы эффективного доступа к элементам. Примеры таких деревьев представлены на рисунке 5.3.

Р ис. 5.3. Бинарные деревья

У каждого узла бинарного дерева может быть 0, 1 или 2 сына. Причем, узел слева называют левым сыном (left child), а справа – правым (right child). Эти наименования связаны с графическим представлением дерева. Двоичное дерево является рекурсивной структурой. Каждый узел – это корень своего собственного поддерева. У него есть сыновья, которые сами являются корнями деревьев, которые называются левым и правым поддеревьями соответственно.

Таким образом, бинарное дерево - это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем. Остальные элементы делятся на два непересекающихся подмножества, каждое из которых, в свою очередь, является бинарным деревом. Эти подмножества называются правым и левым поддеревьями исходного дерева.

Рекурсивное определение двоичного дерева может быть сформулировано следующим образом.

Двоичное дерево - это такое множество узлов B, что

1. B является деревом, если множество узлов пусто (пустое дерево – тоже дерево);

2. B разбивается на три непересекающихся подмножества:

• {R} корневой узел;

• {L₁, L₂, ..., L_m} левое поддерево R;

• {R₁, R₂, ..., R_m} правое поддерево R.

И определение, и процедуры обработки деревьев, как правило, рекурсивны.

Узлы дерева могут быть пронумерованы следующим образом.

Номер корня всегда равен 1, левый потомок получает номер 2, правый - номер 3. Левый потомок узла 2 должен получить номер 4, а правый - 5, левый потомок узла 3 получит номер 6, правый - 7 и т.д. Несуществующие узлы не нумеруются, что обычно не нарушает приведенного порядка. При такой системе нумерации в дереве каждый узел получает уникальный номер.

Полное бинарное дерево уровня n - это дерево, в котором каждый узел уровня n является листом. Причем, каждый узел уровня меньше n имеет непустые правое и левое поддеревья.

Почти полное бинарное дерево представляет собой бинарное дерево, для которого существует неотрицательное целое k такое, что:

1) каждый лист в дереве имеет уровень k или k+1;

2) если узел дерева имеет правого потомка уровня k+1, тогда все его левые потомки, являющиеся листами, также имеют уровень k+1.

В программировании структура бинарного дерева образуется элементами, структура которых приведена на рисунке 5.4. Узел содержит поле данных и два поля с указателями: левым (left) и правым (right), поскольку они указывают на соответствующие поддеревья. Значение NULL является признаком пустого дерева.

Корневой узел определяет входную точку дерева, а поля указателей – узлы следующего уровня. Листовой узел содержит NULL в полях правого и левого указателей. В java узел представляется объектом класса с соответствующей структурой, н апример.

Рис. 5.4. Представление узлов дерева в программировании

class Tree{

public Tree left; // левый указатель

public Tree right; // правый указатель

public int key; // информационное поле целого типа

}

Другой пример – дерево, узел которого хранит его обозначение в виде латинской буквы с номером и числовое поле. Корень обозначается буквой А, узлы 2-го уровня – В, 3-го – С и т.д. Нумерация узлов k-ого уровня выполняется от 1 до 2^k.

Class MyTree{

// Уровень узла

private char Level;

// Номер узла

private int Number;

// Поле узла

private int key; }

При выводе из программы на экран удобно представлять дерево в виде строк текста с отступами. При этом начинают с корня, затем – его левые потомки и только потом – правые. Например, граф на рисунке 5.1 может быть представлен следующим образом.

A

B

E

F

I

J

C

G

D

H

В и В+ деревья

B-дерево является разновидностью дерева поиска. Такая структура была предложена Р. Бэйером и Е. МакКрейтом в 1970 году. Характерной для В-дерева является его малая глубина (высота), обычно равная 2 - 3. Основными свойствами таких деревьев являются: сбалансированность, ветвистость, отсортированность и логарифмическое время выполнения всех стандартных операций (поиск, вставка, удаление). Сбалансированность означает, что все листья находятся на одинаковом расстоянии от корня. В отличие от бинарных, В-деревья допускают большое число потомков для любого узла. Это свойство называется ветвистостью. Благодаря ему, В-деревья очень удобны для хранения крупных последовательных блоков данных, поэтому такая структура часто находит применение в базах данных и файловых системах.

Важным параметром В-дерева является его степень (порядок) m–максимальное число потомков для любого узла. Ключи располагаются между ссылками на потомков и, таким образом, ключей всегда на 1 меньше. В организации В-дерева можно выделить несколько правил:

1. Каждый узел содержит строго меньше m (порядок дерева) потомков.

2. Каждый узел содержит не менее m/2 потомков.

3. Корень может содержать меньше m/2 потомков.

4. У корневого узла есть хотя бы 2 потомка, если он не является листом.

5. Все листья находятся на одном уровне и содержат только данные (ключи).

Пример В-дерева приведен на рисунке 5.5.

Рис. 5.5. Пример В+ дерева. Стрелки идут к потомкам. В ключах записаны числа

Действия с бинарными и В+ деревьями

Узлы дерева обычно используются для хранения информации. Основными операциями над деревьями являются:

1. построение дерева,

2. создание узла,

3. включение узла в дерево,

4. удаление узла из дерева,

5. обход дерева,

6. поиск элементов (узлов).