Представление двоичных деревьев
Рисунок 9. 5. Представление двоичных деревьев.
Эти правила непосредственно транслируются на Пролог следующим образом:
внутри( X, дер( -, X, -) ).
внутри( X, дер( L, -, -) ) :-
внутри( X, L).
внутри( X, дер( -, -, R) ) :-
внутри( X, R).
Очевидно, что цель
внутри( X, nil)
терпит неудачу при любом X.
Посмотрим, как ведет себя наша процедура. Рассмотрим Рисунок 9.4. Цель
внутри( X, Т)
используя механизм возвратов, находит все элементы данных, содержащиеся в множестве, причем обнаруживает их в следующем порядке:
Х = а; Х = b; Х = с; X = d
Теперь рассмотрим вопрос об эффективности. Цель
внутри( а, Т)
достигается сразу же после применения первого предложения процедуры внутри. С другой стороны, цель
внутри( d, Т)
будет успешно достигнута только после нескольких рекурсивных обращений. Аналогично цель
внутри( е, Т)
потерпит неудачу только после того, как будет просмотрено все дерево в результате рекурсивного применения процедуры внутри ко всем поддеревьям дерева Т.
В этом последнем случае мы видим такую же неэффективность, как если бы мы представили множество просто списком. Положение можно улучшить, если между элементами множества существует отношение порядка. Тогда можно упорядочить данные в дереве слева направо в соответствии с этим отношением.
