часов
Самостоятельная работа студента – 90 часов
Виды контроля:
Модульный контроль (тестирование)
Защита
лабораторных работЗАЧЕТ
FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.
Email: Нажмите что бы посмотреть
Список – это линейная динамическая структура данных. Каждый элемент такой структуры, в простейшем случае содержит два поля:
поле данных;
поле – указатель на следующий элемент.
С помощью указателя каждый из элементов списка связывается со следующим элементом (в случае однонаправленного списка)
Голова
Голова
Хвост
Голова
Рисунок 1 – Древовидная структура
Рисунок 2 - Уровень узла и длина пути
Рисунок 3 - Бинарные деревья
На уровне n бинарное дерево может содержать от 1 до 2n узлов. Число узлов, приходящееся на уровень, является показателем плотности дерева. На рисунке 3 дерево А содержит 8 узлов при глубине 3, в то время как дерево B содержит 5 узлов при глубине 4. Последний случай является особой формой, называемой вырожденным (degenerate) деревом, у которого есть единственный лист (E) и каждый нелистовой узел имеет только одного сына.
В случае, если бинарное дерево упорядочено, т.е. для каждого поддерева выполняется условие – значение каждого узла левого поддерева меньше значения корневого узла, а значение любого узла правого поддерева больше или равно значения корневого узла – такое дерево называется бинарным деревом поиска.
Упорядоченность дерева накладывает свои особенности на процедуры создания дерева, добавления и удаления элементов (узлов), а также поиска.
Однако, при сравнении двух рассматриваемых структур по времени выполнения операций добавления элементов следует отметить преимущество линейного списка.
Действительно, при добавлении в бинарное дерево поиска сначала придется найти подходящий лист(выполнив при этом в случае полного дерева log2(N) операций сравнения), тогда как добавление к списку, в случае хранения хвоста происходит сразу же.
Под сбалансированностью понимают то, что для каждого узла дерева высоты обоих его поддеревьев различаются не более чем на 1.
Строго говоря, этот критерий нужно называть AVL-сбалансированностью в отличие от идеальной сбалансированности, когда для каждого узла дерева количества узлов в левом и правом поддеревьях различаются не более чем на 1.
Очевидно, что AVL-деревья имеют структуру, аналогичную бинарным деревьям поиска.
Все операции идентичны описанным для бинарных деревьев, за исключением операций добавления и удаления узлов.
В случае AVL-деревьев, после выполнения каждой из этих операций проверяется соотношение высот левого и правого поддеревьев тех узлов, которые затронула операция(от добавленного/удаленного узла до корня).
Значение, содержащее разность высот правого и левого поддеревьев - показатель сбалансированности - хранится в дополнительном поле каждого узла AVL-дерева.
AVL-деревья со значениями показателя сбалансированности
Алгоритм AVL-вставки
Алгоритм AVL-вставки
Алгоритм AVL-вставки
Алгоритм AVL-вставки
Алгоритм AVL-вставки
Повороты AVL-дерева
Повороты необходимы, когда родительский узел (обозначим его P) становится разбалансированным - баланс фактор становится равен 2 или -2.
Одинарный поворот вправо (single right rotation) происходит тогда, когда родительский узел P и его левый сын (обозначим его LC) начинают перевешивать влево после вставки узла в позицию X.
Алгоритм AVL-вставки. Одинарный поворот.
Одинарный поворот уравновешивает как родителя, так и его левого сына.
Алгоритм AVL-вставки. Двойной поворот.
1. Узел NP замещает родительский узел.
2. Бывший родитель P становится правым сыном NP .
3. Осиротевшие поддеревья NP распределяются к LC и P .
Если в дереве постоянно происходят вставки и удаления элементов, эти операции могут значительно снизить быстродействие.
С другой стороны, если данные превращают бинарное дерево поиска в вырожденное, то теряется поисковая эффективность.
Таким образом, применение AVL-деревьев целесообразно в тех случаях, когда поиск является доминирующей операцией.
В таких случаях сначала происходит построение дерева, а потом производится поиск по этому дереву с небольшим количеством изменений.
Если структуры данных, например, бинарное дерево поиска или AVL-дерево, расположены не в оперативной памяти, а на диске, то они становятся малоэффективными.
При работе с данными, хранящимися на внешних носителях, целесообразно сокращать количество обращений к носителю.
Если предположить, что в одном узле дерева, хранящегося на диске, будет расположен не один, а несколько элементов – узел в этом случае называется страницей дерева и за одно обращение к диску будет считываться целая страница, то число обращений к диску при поиске существенно уменьшится.
Например, при N=1млн., число обращений к обычному дереву равно примерно 20(log2106≈20), а при постраничном чтении, например, по 7 элементов, число обращений сократится в 3 раза, что ускорит поиск в 3 раза.
Определение: Б-деревом порядка n называется динамическая структура обладающая следующими свойствами:
Каждая страница имеет не более 2n элементов
Каждая страница, кроме корневой, имеет не менее n элементов. Корневая страница может иметь от 1 до 2n элементов
Каждая страница является либо листовой, либо содержит m+1 потомков, где m - число элементов на этой странице
Все листья находятся на одном уровне
Память в B-дереве всегда используется минимум на 50%, так как страницы всегда заполнены как минимум наполовину!
Если страница уже считана в оперативную память и можно воспользоваться обычными методами поиска среди ключей ki ... km.
Если m достаточно большое, то это может быть двоичный поиск, если же оно мало, то можно воспользоваться простым последовательным перебором.
Если поиск элемента х на странице неудачен, то мы попадаем в одну из следующих ситуаций:
ki < х < ki+1 для 1 ≤ i < m. Поиск продолжается на странице pi.
km < х. Поиск продолжается на странице рm.
х < k1. Поиск продолжается на странице р0.
Включение элемента в B-дерево
Если новый элемент нужно поместить на страницу с m < 2n элементами, то процесс включения элемента затрагивает лишь одну страницу B-дерева.
Включение в заполненную страницу затрагивает структуру дерева и может привести к появлению новых страниц.
Исключение элемента из B-дерева
В первом случае, удаление элемента с листовой страницы не вызовет затруднений, если эта страница содержит более n элементов.
Если же количество элементов на странице после удаления станет меньше n, то необходимо проделать некоторые действия, чтобы предотвратить нарушение второго условия B-дерева (m>=n).
В этом случае для текущей страницы необходимо позаимствовать элемент с одной из соседних страниц. Если соседняя страница содержит более n элементов, то происходит перемещение крайнего элемента (ближнего к текущей странице) в родительскую страницу, а элемент из родительской страницы в текущую.
Исключение элемента из B-дерева
Так как общее число элементов на двух соседних страницах после удаления становится равным 2n-1, то, забирая элемент с родительской страницы, получим одну страницу содержащую 2n элементов. При этом вторая освободившаяся страница уничтожается. Процесс слияния страниц в точности обратен процессу разделения страницы.
Потери времени на повторное упорядочивание таблицы могут значительно превышать выигрыш от сокращения времени поиска. Поэтому для сокращения времени доступа к данным в таблицах часто используется так называемое случайное упорядочивание или хеширование.
При этом данные организуются в виде таблицы при помощи хеш-функции h, используемой для “вычисления” адреса по значению ключа.
Хеш-таблицы - один из наиболее эффективных способов реализации словарей (словарь - абстрактный тип данных (множеств) с операторами вставки, удаления и проверки членства INSERT, DELETE и MEMBER).
В случае заранее неопределенного множества значений ключей и ограниченной длины таблицы подбор совершенной функции затруднителен.
Ключи и хеш-функция
Предположим, Key – положительное целое, а HF(Key) – значение младшей цифры числа Key. Тогда диапазон индексов равен 0-9.
Например, если Key = 49, HF(Key) = HF(49) = 9.
Эта хеш-функция в качестве возвращаемого значения использует остаток от деления на 10.
// Хеш-функция, возвращающая младшую цифру ключа
int HF(int key){ return key % 10;}
Коллизии и методы разрешения коллизий
Для разрешения коллизий используются различные методы, которые в основном сводятся к методам “цепочек“ и “открытой адресации“.
Процедура удаления из таблицы сводится к поиску элемента и его удалению из цепочки переполнения.
Линейное опробование сводится к последовательному перебору элементов таблицы с некоторым фиксированным шагом a=h(key) + c*i , где i – номер попытки разрешить коллизию. При шаге равном единице происходит последовательный перебор всех элементов после текущего.
Поиск:
i = 0
a = h(key) + i*c
Если t(a) = key, то стоп элемент найден
Если t(a) = свободно, то стоп элемент не найден
i = i + 1, перейти к шагу 2
В том случае, если за удаляемым элементом в результате разрешения коллизий были размещены элементы с другими ключами, то поиск этих элементов после удаления всегда будет давать отрицательный результат, так как алгоритм поиска останавливается на первом элементе, находящемся в состоянии свободно.
Скорректировать эту ситуацию можно различными способами. Наилучший из них состоит в том, что для элементов хеш-таблицы добавляется состояние “удалено”. Данное состояние в процессе поиска интерпретируется, как занято, а в процессе добавления - как свободно.