Сделайте

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

Для этого вначале формируется исходная упорядоченная таблица из N имен, представляющих собой четные положительные числа в пределах от 2 до 2N, и представляется соответствующей структурой данных (массив, дерево). Значение величины N выбирается исходя из соображений возможности фиксирования времени вычислений (по возможности). Время, затрачиваемое на заполнение исходной таблицы, при исследовании алгоритмов не учитывается.

Исследование методов поиска состоит в проведении K (K ≥ 1000) статистических испытаний. Каждое испытание включает в себя генерацию случайного ключа поиска, прогон для этого ключа всех исследуемых алгоритмов (программ), подсчитывая при этом число сравнений имен и фиксируя (по возможности) время поиска. Полученные результаты суммируются с соответствующими значениями, вычисленными на предыдущих испытаниях, т. е. идет накопление значений. После проведения всех K испытаний деление полученных значений на K дает средние значения соответствующих величин, которые заносятся в таблицу результатов.

Такие исследования проводятся для различных значений N (число размеров таблиц ≥ 5). По полученным данным необходимо построить аппроксимирующие функции и вычислить аналитические зависимости времени поиска от N.

Для исследования успешного поиска генерируются случайные четные ключи в диапазоне от 2 до 2N, а безуспешного поиска – нечетные ключи в диапазоне от 1 до 2N + 1.

2. Исследовать алгоритмы включения и исключения для динамических таблиц.

Для этого вначале создается либо пустое дерево поиска, либо можно воспользоваться деревом, построенным в предыдущем пункте (содержит только четные ключи).

Исследование состоит в проведении K (K ≥ 1000) статистических испытаний. Каждое испытание включает в себя генерацию случайного запроса (ключа поиска) в диапазоне от 1 до N. Обработка запроса заключается в следующем: если ключ уже есть в дереве поиска, то соответствующий узел исключается из дерева, в противном случае – выполняется операция включения нового узла. При этом накапливаются значения следующих данных: число операций вращения при балансировке (для АВЛ-деревьев двойное вращение считать как два вращения) и время (по возможности) обработки запроса. После проведения всех K испытаний деление полученных значений на K дает средние значения соответствующих величин, которые заносятся в таблицу результатов.

Рекомендуется также в качестве результата исследования определить максимальное число вращений, потребовавшихся для балансировки дерева при проведении этих K испытаний.

Такие исследования проводятся для различных значений N (число размеров таблиц ≥ 5).

ДЛЯ :

1. Последовательный поиск в упорядоченной таблице.

2. Обычный бинарный поиск.

3. Однородный бинарный поиск с вычислением значений .

7. Интерполяционный поиск.

8. Поиск в обычном дереве бинарного поиска (без балансировки).

11. Поиск в АВЛ-дереве (в узле есть поле Father для указателя на отца).

12. Поиск в RB-дереве (в узле есть поле Father для указателя на отца).

13. Цифровой поиск.

14. Поиск с хешированием.