Как проверить, является ли двоичное дерево BST в O (nlgn)?

Question

У меня есть проблема в моем упражнении, когда я хочу дать алгоритм, который проверяет, является ли двоичное дерево BST или нет.

Он также хочет решить его с помощью метода «разделяй и властвуй», поэтому я думаю, что моя рекурсивная функция должнабыть чем-то вроде this:

T(n) = 2T(n/2) + O(n)

, но я понятия не имею, как спроектировать объединяющуюся часть в порядке O(n).

Кто-нибудь получилесть идеи?

Answer 1

Обход дерева O (n) .Проверка сортировки списка: O (n) . O (n) находится в O (n log n) .

В соответствии с тем, что вы сказали, часть слияния должна быть O (1) , а не O (n) , снова давая вам O (n) решение в целом: если левое поддерево является BST, а правое поддерево является BST, а левое подкорень меньше, чем root, а root не больше правого подкорня, тогдаэто дерево является BST:

T(n) = T(m) + T(n-m-1) + T(1)    where   m < n   is the count of the left subtree

Плюс очевидная обработка пустых поддеревьев в крайнем случае.