Математические методы в библиотечной работе. Елизаров А.М - 208 стр.

 ного" хранения данных в виде картотек, книг и т. п.
 предназначенных для непосредственного чтения чело-
 веком. В то же время для „машинного" хранения и
 поиска в большинстве случаев оказывается более
 эффективным древесный порядок. Рассмотрим не-
 сколько примеров.
 При выборе способа организации данных приходится,
 в первую очередь, учитывать два фактора: скорость
 поиска и удобство пополнения массива данных. С
 обеих точек зрения последовательная организация
 массива оказывается неэффективной. Значительно
 эффективнее организация данных по схеме
 бинарного дерева, позволяющая осуществить быстрый
 поиск и производить пополнение массива новыми
                     данными без перестройки уже
                     имеющейся системы упорядочения.
                     Пусть единицами данных являются
                     числа, например, 70, 820, 850, 68, 900,
                     30, 250, 410, упорядочиваемые в
                     порядке поступления.
                     Принцип упорядочения по схеме
                     бинарного дерева состоит в сле-
                     дующем: первая запись аi (число 70)
                     объявляется входом в массив
 Рис. 68. Упорядоче- (корнем дерева). Каждое после-
 ние по схеме бинар-
                      дующее число аi сравнивается с
 ного дерева          первым и связывается с ним пра-
вой подчиняющей стрелкой, если ai>a1, либо левой
подчиняющей стрелкой, если a i < а1 (считаем, что
двух одинаковых записей в массиве нет). Если соот-
ветствующая cтрелка уже проведена, аi сравнивается с
числом, присоединенным этой стрелкой, с теми же
исходами и т. д. На рис. 68 показано упорядочение
данного набора чисел.
 Если допустить, что число 70 по величине соот-
вeтствует середине массива и числа во входном маc-
сиве хорошо перемешаны (а это означает, что дерево
растет равномерно по всем направлениям), то поиск
нужной записи в массиве из N записей будет произ-
водиться в среднем за n=log2 N шагов.
   Довольно часто поиск должен производиться в
больших, массивах данных, отличающихся только по
некоторым из своих элементов. В этом случае можно
упорядочить такие данные по схеме дерева. Напри-
208