Программирование на языке ПРОЛОГ для искуственного интеллекта




Представление множеств двоичными деревьями - часть 3


достигается сразу же после применения первого предложения процедуры внутри. С другой стороны, цель

        внутри( d, Т)

будет успешно достигнута только после нескольких рекурсивных обращений. Аналогично цель

        внутри( е, Т)

потерпит неудачу только после того, как будет просмотрено все дерево в результате рекурсивного применения процедуры внутри ко всем поддеревьям дерева Т.

В этом последнем случае мы видим такую же неэффективность, как если бы мы представили множество просто списком. Положение можно улучшить, если между элементами множества существует отношение порядка. Тогда можно упорядочить данные в дереве слева направо в соответствии с этим отношением.

fig9_6.gif (1219 bytes)

Рис. 9. 6.  Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути 5-->8-->6.

Будем говорить, что непустое дерево дер( Лев, X, Прав) упорядочено слева направо, если

(1)        все вершины левого поддерева Лев меньше X;

(2)        все вершины правого поддерева Прав больше X;

(3)        оба поддерева упорядочены.

Будем называть такое двоичное дерево двоичным справочником. Пример показан на рис. 9.6.

Преимущество упорядочивания состоит в том, что для поиска некоторого объекта в двоичном справочнике всегда достаточно просмотреть не более одного поддерева. Экономия при поиске объекта Х достигается за счет того, что, сравнив Х с корнем, мы можем сразу же отбросить одно из поддеревьев. Например, пусть мы ищем элемент 6 в дереве, изображенной на рис. 9.6. Мы начинаем с корня 5, сравниваем 6 с 5, получаем 6 > 5. Поскольку все элементы данных в левом поддереве должны быть меньше, чем 5, единственная область, в которой еще осталась возможность найти элемент 6, - это правое поддерево. Продолжаем поиск в правом поддереве, переходя к вершине 8, и т.д.

Общий метод поиска в двоичном справочнике состоит в следующем:




Содержание  Назад  Вперед