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

И. П. Толстой Княжна (1726) П.М. Ртищева А.И.Щеткина Генеалогическое древо графа Льва Николаевича Толстого име­ ет вид, изображенный на рис. 2.25. Бинарны й п о и ск . Бинарные деревья применяются в информа­ тике для одной из самых распространенных в прикладных науках операций — поиску. К нему прибегают, когда необходимо найти в некотором упорядоченном массиве (множестве) определенную информацию. Например, в телефонном справочнике — номер ка­ кого-нибудь абонента, в словаре — определенное слово, в файле — сведения о зарплате сотрудников некоторого предприятия, сведе­ ния о зарплате отдельного работника и т.д. Последовательный, или линейный, поиск является наиболее общим и простым методом выявления интересующей информа­ ции: каждый элемент множества проверяется на соответствие за­ данным условиям. Если множество неупорядочено, то такой про­ цесс будет носить случайный характер. Если множество было пред­ варительно упорядочено (распределение по алфавиту фамилий в телефонном справочнике, слов в словаре, распределение служа­ щих предприятия по табельным номерам в информации о зарпла­ те), то удобнее использовать другой, более эффективный метод — бинарный поиск. 94