243
правки
Изменения
→Задачи на поиск максимального BST в заданном двоичном дереве
{{Задача
|definition = Найти в данном дереве такую вершину, что поддерево, для которого она является будет корнем, будет максимальным деревом дерева поискас наибольшим количеством вершин.
}}
Если мы будем приведённым выше способом проверять каждую вершину, мы справимся с задачей за <tex>O(n^2)</tex>. Но её можно решить за <tex>O(n)</tex>, идя от корня и проверяя все вершины по одному разу, основываясь на следующих фактах:
