Разработка компиляторов
Подстановка деревьев
Для дальнейших рассуждений введем следующие обозначения:
- через root(t) обозначим корень дерева t
- через t(v) обозначим поддерево дерева t с корнем v (таким образом, t(root(t))=t)
- через sons(v) обозначим множество сыновей вершины v
- через son(v,i) обозачим i-го сына вершины v
Для пары деревьев в одном и том же алфавите можно определить операцию подстановки. Для этого в одном из них выбирается лист, который затем заменяется на корень другого дерева. Если подставляется вместо вершины v в дерево , то результат подстановки будем обозначать.
