Наклонный текст обозначает дополнительные материалы
Таблицы: когда удобно, а когда нет. Разнообразие структур данных.
Поиск минимального элемента в массиве; проверка целого числа на простоту. Определение O для алгоритмов с разными операциями: смещение max элемента пузырьком в конец массива. Методы сортировки пузырьком и слияниями. Не всегда стоит использовать «лучшие» в смысле О методы: сортировка маленьких массивов, почти отсортированных массивов, поиск медианы. Р-и NP-задачи.
Определение, названия узлов. Бинарное дерево, бинарное дерево поиска. Глубина дерева, сбалансированное дерево.
«Проекция» сбалансированного дерева поиска на упорядоченный массив. Сбоку показана глубина дерева.
Один из популярных алгоритмов балансировки — красно-черные деревья. В C++ они используются в std::map и std::set. Другие интересные деревья: К-мерные дерева, В-деревья.
Хэш-функции, скорость доступа, расход памяти. Парадокс дней рождений (р(21) = 0,44) и коллизии. Способы разрешения коллизий: цепочка и открытая адресация. В Python dict, set; С ++ Std:: unordered-map / set.