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