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

Специальный случай 2: оба дерева, <math>T_1 \;</math> и <math>T_2 \;</math>, являются полными бинарными деревьями. Для каждой вершины v дерева <math>T_2 \;</math> только определенные вершины u в <math>T_1 \;</math> могут быть отображены на v практичным образом, в том смысле, что поддерево <math>T_1 \;</math> с корнем в u и поддерево <math>T_2 \;</math> с корнем в v имеют непустое поддерево соответствия. Существует <math>O(n \; log^2 \; n)</math> таких пар (u, v), что можно показать следующим образом. Заметим, что для того, чтобы две вершины (u, v) составляли такую пару, поддерево <math>T_1 \;</math> с корнем в u и поддерево <math>T_2 \;</math> с корнем в v должны иметь общую метку листа. Для каждой метки существуют только <math>O(log^2 \; n) \;</math> таких пар, полученных сопряжением каждого потомка листа с этой меткой в дереве <math>T_1 \;</math> с каждым потомком листа с этой меткой в дереве <math>T_2 \;</math>. Таким образом, общее число интересных пар составляет <math>O(n \; log^2 \; n)</math>. Для каждой пары вычисление MAST требует O(1) времени, поскольку вопрос заключается просто в нахождении лучшего способа сопряжения их потомков.