Анализ результатов
1. Влияние порядка входных данных на вставку в BST
Эффективность двоичного дерева поиска сильно зависит от того, насколько оно сбалансировано.
Когда записи поступают в случайном порядке, дерево получается относительно равномерным: его высота пропорциональна O(log n), а время вставки одного элемента остаётся небольшим.
Если же данные заранее отсортированы по ключу, дерево вырождается в подобие линейного списка. Каждая новая запись вставляется на самое дно, что даёт:

вычислительную сложность одной вставки — O(n);

общую сложность вставки всех элементов — O(n²).

Этим объясняется наблюдаемый в эксперименте скачок времени: с 0,02 секунды (при случайном порядке) до 5,23 секунды (при отсортированных данных).

2. Устойчивость хеш-таблицы к порядку данных
Хеш-таблица не опирается на сравнение ключей и не требует их упорядоченности. Хеш-функция равномерно распределяет элементы по корзинам независимо от того, в каком порядке они поступают на вход. В результате все основные операции сохраняют асимптотику в среднем O(1):

вставка – за константное время;

поиск – за константное время;

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

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

3. Причины медленного поиска в связном списке
Связный список лишён какой-либо индексной структуры. Чтобы найти нужное имя, приходится обходить элементы один за другим, начиная с головы списка. Поэтому время выполнения базовых операций линейно зависит от количества записей:

поиск — O(n);

вставка в конец (без хвостового указателя) — O(n);

удаление — O(n).

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

4. Особенности удаления в каждой структуре
Связный список

Находим узел, предшествующий удаляемому.

Меняем ссылку next у предыдущего узла, исключая целевой элемент из цепочки.

Сложность: O(n).

Хеш-таблица

Вычисляется номер корзины.

Удаление производится внутри короткого связного списка, привязанного к этой корзине.

Средняя сложность: O(1).

Двоичное дерево поиска

Если у узла нет потомков, просто убираем его.

Если один потомок — заменяем узел этим потомком.

Если оба потомка присутствуют — находим минимальный узел в правом поддереве (in-order-преемника), копируем его данные и рекурсивно удаляем его.

Сложность: O(log n) в сбалансированном дереве и O(n) в вырожденном.

5. Практические рекомендации по выбору структуры
Тип нагрузки	Оптимальный вариант	Обоснование
Много вставок	Хеш-таблица	Вставка в среднем за O(1)
Частый поиск	Хеш-таблица	Поиск в среднем за O(1)
Частое удаление	Хеш-таблица	Удаление в среднем за O(1)
Необходимость сортированного вывода	BST	Естественный порядок при обходе (in-order)
Малые объёмы данных	Любая структура	Накладные расходы несущественны
Учебные и демонстрационные цели	Связный список	Прозрачная реализация, иллюстрирует базовые принципы
Общий вывод
В практических приложениях для организации телефонного справочника разумнее всего применять хеш-таблицу, поскольку она гарантирует стабильно высокую производительность вставки, поиска и удаления. Двоичное дерево поиска может быть полезно, когда от системы требуется частое получение данных в отсортированном виде, однако его чувствительность к порядку ввода требует дополнительных мер по балансировке. Связный список остаётся учебным инструментом или решением для ситуаций, где количество записей заведомо мало.