Поддерево максимального соответствия: различия между версиями

Оптимизация 1: время исполнения алгоритма для специального случая полных деревьев улучшается до O(n log n) следующим образом. Пара вершин (u, v), и 2 T1, v 2 T2, считается интересной, если существует поддерево соответствия, отображающее u на v. Как показано ниже, для полных деревьев общее число интересных пар (u, v) составляет всего O(nlog n). Рассмотрим вершину v в дереве T2. Пусть L2 – множество листьев, являющихся потомками v. Пусть L1 – множество тех листьев T1, которые имеют те же метки, что и листья в L2. Отображены на v могут быть только вершины u, принадлежащие к поддереву T1, порожденному L1. Количество таких вершин составляет O(размер поддерева T2 с корнем в v). Таким образом, общее число интересных пар представляет собой сумму всех поддеревьев T2, или O(n log n).