Методы поиска в основной памяти
В этой части книги будут обсуждаться структуры данных в основной памяти и методы их использования, предназначенные для поиска данных в соответствии со значениями их ключей. Эта задача является не менее распространенной в программировании, чем внутренняя сортировка данных.
Главным образом, распространены два подхода - поиск в динамических древовидных структурах и поиск в таблицах на основе хэширования. Рассмотрению разновидностей этих подходов и посвящены следующие два раздела.
Заметим, что мы намеренно выделили в отдельную часть структуры данных и методы поиска данных во внешней памяти. Несмотря на использование того же набора терминов (деревья и хэширование) поиск во внешней памяти и критерии оценки эффективности алгоритмов существенно отличаются от тех, которые применимы в случае расположения данных в основной памяти.
