10.5. Сумма ячеек

Пусть дано множество

C = {c1 .. cN}

ячеек некоторого дерева T таких, что:

1. корни никаких ячеек между собой не совпадают
2. никакие листья никаких ячеек между собой не совпадают
3. если в множестве C только одна ячейка, то она считается корневой и базовой одновременно
4. если в множестве C более одной ячейки, то:
   1. корень только одной из этих ячеек, называемой корневой, не совпадает ни с одним листом никакой другой ячейки из этого множества C
   2. у ячеек, корневыми не являющихся, корни совпадают ровно с одним из листьев некоторой другой ячейки
   3. только у базовых ячеек все их листья не совпадают ни с каким корнем никакой другой ячейки
   4. у ячеек, не являющихся базовыми, все или часть листьев совпадают с корнями некоторых других ячеек

В этом случае дерево

TC = <NDC, AC> = c1 + .. + cN = ∑ci (i=1..N)

образованное из множества NDC вершин и множества AC дуг указанных ячеек, называется суммой ячеек c1 .. cN дерева T.

Иначе говоря, все узлы TC за исключением его корня являются одновременно и листьями и корнями связываемых ею (соподчинённых) ячеек. █

Назад Вперёд