Изменения

Рассмотрим как можно улучшить данный алгоритм:

*Зададим некую функцию <tex>S(n) = \dfrac{1}{4} \log n</tex>

*Забудем на время про удаленные поддеревья, для оставшегося дерева наш алгоритм даст < <tex>O(\dfrac{n}{S(n)} \log n + n), O(1)</tex> >. Что дает нам алгоритм за

< <tex>O(n), O(1) </tex>>. Для удаленных поддеревьев же выполним полный предподсчет: таких деревьев не более чем <tex>2^{2S(n)}</tex>, что дает ассимптотику предподсчета

В итоге полученный алгоритм действительно работает за <<tex>O(n), O(1)</tex>>.