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

исключающих подмножества по какому-то признаку (так называ­ емое дихотомическое деление). Для отца А — сыновья В и С, при ­ чем В —левый, а С — правый потомки. Строго бинарным деревом называется такой граф (рис. 2.16), у которого каждый узел, не являющийся листом, содержит два и только два поддерева — л е ­ вое и правое. Бинарное дерево уровня я называется полным, если каждый его узел уровня я является листом, а каждый узел уровня мень­ ше, чем я, имеет непустое левое и правое поддеревья. Примером полного бинарного дерева служит таблица розыгрыша соревнова­ ния по олимпийской системе («плей-офф»). На рис. 2.17 приведе­ на таблица розыгрыша Кубка мира по футболу 2010 г., начиная со стадии четвертьфиналов (указан корень V0 — Испания). Бинарные деревья применяются в информатике для поиска од ­ ного из двух возможных вариантов ответа. Например, при поиске данных, когда необходимо сравнить каждый элемент списка с об ­ разцом, и если значения совпадают, то процесс поиска завершен, Гана Уругвай Нидерланды Уругвай Бразилия Нидерланды Нидерланды ФРГ Аргентина ФРГ Испания Парагвай Испания Испания Испания Рис. 2.17. Бинарное дерево для представления розыгрыша Кубка мира по футболу 2010 г. 4 * 83