Изменения

Перейти к: навигация, поиск

Дерево поиска, наивная реализация

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

Навигация