Способы обхода бинарного дерева: нисходящий, восходящий, смешанный.

Нисходящий – от корневой вершины вниз к листьям.

Восходящий – от листьев вверх к корню.

Смешанный – от самого левого листа дерева через корень к самому правому листу.

Поиск минимальной длины ветви дерева.(?)

Сбалансированные деревья. Показатель сбалансированности. AVL-деревья.

Дерево, для каждого узла которого высота 2-х его поддеревьев различается не более чем на 1.

Узлы: левоперевешивающие(самый длинный путь по левому поддереву на 1 больше чем по правому), правоперевешивающие, сбалансированные.

Виды балансировки деревьев. Балансировка через массив.

Операции балансировки: однократный правый(RR), однократный левый(LL), двукратный лево-правый(LR), двукратный право-левый(RL) повороты узлов.

Красно-черные деревья.

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

Приложения деревьев. Дерево Хаффмана.

Бинарная куча. Проверка основного свойства кучи.

Массив, обладающий определенными свойствами упорядоченности. По массиву строится дерево причем для всех i родитель >= потомкам. Проверка основного свойства кучи осуществляется с помощью процедуры heapify(проверяет, если дети >родителя –меняет местами).

Бинарная куча. Определение родительской и дочерних вершин.

Для каждого элемента массива можно определить левую и правую вершины, кроме листьев, и наоборот, для всех, кроме корня можно определить родителя.

Бинарная куча. Алгоритм построения кучи из произвольного массива.

buildheap(последовательно вызывает heapify для всех элементов, в порядке убывания номера).

Бинарная куча. Извлечение наибольшего элемента. Оценка сложности

Extractmax(извлекает максимальный элемент не нарушая основного св-ва).

Бинарная куча. Добавление элемента.

insertheap – добавляет новый элемент не нарушая основного свойства.

Обзор куч: левосторонние, биномиальные, фибоначевы, тонкие и др. Оценка сложности(?)

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

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

Хэш-таблицы. Понятие, назначение и принцип организации.

Сочетание массивов и списков, структура для хранения и получения динамических данных.

Работа с одним большим множеством сводится к работе с массивом небольших множеств.

Алгоритмы вычисления хэш-функции.

Преобразовывает ключи в адреса таблицы.

40. Хэш-таблицы. Прямая адресация в хэш-таблицах.

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

Хэш-таблицы. Коллизии. Построение цепочек.

Ситуация когда для различных ключей, получается одно и то же хеш-значение. Разрешается с помощью цепочек. Элементы множества, которым соответствует одно и то же хеш-значение, связываются в цепочку-список.

42. Хэш-таблицы. Открытая адресация в хэш-таблицах. Способы вычисления последовательности испробованных мест при открытой адресации (линейный, квадратичный).

Хеш-списков нет, все записи хранятся в самой хеш-таблице, каждая ячейка хранит либо значение динамического множества, либо NULL.

Хэш-таблицы. Основные свойства и эффективность.

Основной параметр, от которого зависит время выполнения – коэффициент заполнения(число хранимых эл-тов/размер массива).

Задача поиска подстрок, простейший алгоритм.(?)

Задача поиска подстрок. Алгоритм Хорспула. Алгоритм Карпа-Рабина.(?)

Задача поиска подстрок. Алгоритм Бойера-Мура. Алгоритм Кнута-Морриса-Пратта(?)