Разработка компиляторов

       

Подстановка деревьев


Для дальнейших рассуждений введем следующие обозначения:

  • через root(t) обозначим корень дерева t
  • через t(v) обозначим поддерево дерева t с корнем v (таким образом, t(root(t))=t)
  • через sons(v) обозначим множество сыновей вершины v
  • через son(v,i) обозачим i-го сына вершины v

Для пары деревьев в одном и том же алфавите можно определить операцию подстановки. Для этого в одном из них выбирается лист, который затем заменяется на корень другого дерева. Если подставляется вместо вершины v в дерево , то результат подстановки будем обозначать.



Содержание раздела