Спирина, М.С. Дискретная математика

Рис. 2.26. Блок-схема иерархического представления видов вычислительных машин Бинарный поиск основан на методе половинного деления. По­ иск начинается с середины множества. Если первый же элемент удовлетворяет условию, то процесс поиска завершен, если не удовлетворяет, то процесс продолжается в любой из половин. Если искомый элемент так и не найден, то анализируется вторая поло­ вина до тех пор, пока не обнаружится соответствие найденного элемента заданным условиям. Бинарные деревья необходимы, когда делается выбор одной альтернативы из двух. Пусть надо найти дубликаты всех чисел в некотором списке. Можно применить сравнение каждого числа с предшествующим на предмет «был — не был». Но тогда необходимо большое число сравнений. Использование бинарных деревьев (БД) укорачивает процедуру сравнения. Считывается новое число и помещается в узел — будущий корень нового БД. Каждое последующее число из списка сравнивается с числом в корне БД. Если эти значения со­ впадают, то дубликат найден, если число меньше корня, то про­ цесс продолжается в правом поддереве, если больше — в левом поддереве. Различные виды графов и деревьев находят широкое приме­ нение в учебном процессе. Поэтому первоначальные сведения о них необходимы для успешного обучения в различных областях, так как с их помощью часто передается учебная информация. Например, основные классы ЭВМ можно изобразить в виде гра­ фа (рис. 2.26). На процедуре бинарного поиска с использованием графа- дерева основана работа ЭВМ с базой данных. Информация о базе может быть представлена несколькими способами, в том числе матричным. Так называемые реляционные базы хранят различную информацию в форме таблиц, причем порядок строк и столбцов задается при вводе данных. В базах возможна дли ­ тельная работа с информацией , ее реорганизация и обновле­ ние. С помощью автоматического поиска данных происходит их 95