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