Сложность времени - алгоритм, чтобы найти самый низкий общий предок всех самых глубоких листьев

Question

Это утверждение проблем, которое я нашел сегодня.

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

Я придумал правильный алгоритм, но я хотел бы подтвердить время работы этого подхода.

Алгоритм выглядит следующим образом:

1. Пересматривать дерево и найти самый глубокий уровень дерева, DMAX .
2. Пересматривать дерево и находить все листья на глубине dmax .
3. Учитывая, что lca (a, b, c) = lca (lca (a, b), c) < / strong>, пройти все узлы, найденные на шаге 2 и рассчитайте LCA.

Подпрограмма для lca (a, b) прост. Начиная с A , пройдите до корня и храните каждое посещаемое узел в хеш-слое. Затем, начиная с b , поднимитесь, пока не найдете узел, который содержится в хеш-метастере.

Я знаю, что первые два этапа алгоритма являются как O (n) , где n соответствует количеству узлов в дереве. Тем не менее, я не уверен в последнем шаге.

lca (a, b) подпрограмма имеет линейную сложность. Но сколько узлов, в худшем сценарии, можно найти на шаге 2?.

Интуитивно, я бы утвердовал, что он должен быть намного меньше, чем n узлов.

Answer 1

Как объяснил @rick Decker, вы могли бы иметь $ N / 2 $ листья на максимальной глубине в одном случае. В этом случае шаг 3 представляет собой $ O (n \ log n) $ . Это сообщение показывает худший случай. Рассмотрим дерево $ T $ состоит из цепочки N $ N / 2 $ , где остальные N $ N / 2 $ узлы прикреплены как сбалансированное дерево в нижней части цепи. Это дает каждую глубину листа $ n / 2 + \ log_2 (n)=theta (n) $ с $ n / 4 $ листья на глубине $ \ theta (n) $ У нас есть $ \ theta (n ^ 2) $ Время выполнения для шага 3 в этом случае. Это асимптотически худший случай, поскольку у нас есть $ N $ Узлы на максимальной глубине $ n $ .

Есть лучший способ сделать это. Давайте определим функцию $ f $

$ f (v)=начать {случаи} V & \ Text {Если} \ Quad \ TextTt {height} (v.left)=texttt {height} (v.right) \\ f (v.left) & \ text {если} \ Quad \ texttt {height} (v.left)> \ texttt {height} (v.right) \\ f (v.right) & \ text {если} \ Quad \ texttt {height} (v.left) <\ texttt {height} (v.right) \ end {случаи} $

Если высота детей узла $ v $ одинаковы, то четко $ v $ Является ли LCA самых глубоких узлов поддерева, укоренившись на $ v $ . Если левый поддерее выше, то мы хотим, мы хотим, чтобы LCA самых глубоких узлов поддерева, укоренившись на $ v.left $ , поскольку они глубже, чем самые глубокие узлы в Подмер укоренившись на $ v.right $ . Тот же логика следует за $ v.right $ , когда он выше.

Значения для $ \ texttt {height} $ и $ f (v) $ может быть Вычисляется в прохождении после порядка $ T $ в линейном времени.

Вызов

$ f (root) $ должен вернуть LCA самых глубоких узлов в дереве.

Answer 2

Ну, я не знаю, что вы намереваетесь «гораздо меньше, чем», но ясно, что вы можете иметь о $ N / 2 $ на максимальной глубине: Возьмите полное бинарное дерево, например, с самым низким уровнем.

Answer 3

Я бы написал функцию, которая для каждого дерева рассчитывает самый низкий общий предком всех самых глубоких узлов, и высота дерева.Это довольно просто:

Если корня R не имеет левой или правой ветви, то высота 1, а общий предком является R. Если корня R имеет левую или правую ветвь, затем рассчитать высоту и самым низким распространенным предком этой ветви иВысота с корнем R - одна выше, но самый низкий общий предком одинаково.

Если есть левый и правая ветвь, затем рассчитайте высоту и самым низким распространенным предком обоих ветвей.Если высота отличаются, то мы возвращаемся (высота + 1) плюс самый низкий предок этой ветви.Если высоты одинаковы, то мы возвращаемся (высота + 1), а r как самый низкий общий предок.

Это должно принять шаги CN небольшую константу c, если количество узлов N., и поскольку мы должны посещать каждый узел N (по крайней мере, чтобы узнать, что у него нет ветвей), это не может быть улучшено.