- Реализовать поиск заданного элемента в массиве (необходимо найти ВСЕ вхождения) объектов по ключу в соответствии с вариантом (структурой данных из ЛР1 (Passenger), ключом является первое НЕ числовое поле объекта (name)) следующими методами:
- линейный поиск
- с помощью бинарного дерева поиска
- с помощью красно-черного дерева
- с помощью хэш таблицы
Все методы необходимо реализовать самостоятельно. Предполагается, что в исходном массиве данных ключи не уникальны.
-
Для хэш таблицы необходимо реализовать хэш функцию и метод разрешения коллизий. Подсчитать число коллизий хэш функции и построить график зависимости от размерности массива.
-
Выполнить поиск не менее 10 раз на массивах разных размерностей от 100 до 1000000. Засечь (программно) время поиска для всех способов. По полученным точкам построить сравнительные графики зависимости времени поиска от размерности массива.
-
Записать входные данные в ассоциативный массив multimap<key, object> и сравнить время поиска по ключу в нем с временем поиска из п.3. Добавить данные по времени поиска в ассоциативном массиве в общее сравнение с остальными способами и построить график зависимости времени поиска от размерности массива.