Complexidade de tempo - Algoritmo para encontrar o menor ancestral comum de todas as folhas mais profundas

Question

Esta é a declaração do problema que encontrei hoje.

Dada uma árvore binária, encontre o menor ancestral comum de todas as folhas mais profundas.

Eu vim com um algoritmo correto, mas gostaria de confirmar o tempo de execução dessa abordagem.

O algoritmo é o seguinte:

.
1. atravessar a árvore e encontrar o nível mais profundo da árvore, dmax .
2. atravessar a árvore e encontrar todas as folhas em profundidade dmax .
3. Dado que lca (a, b, c) = lca (LCA (A, B), C) < / forte>, atravessar todos os nós encontrados na etapa 2 e calcular a LCA.

A sub-rotina para lca (a, b) é simples. A partir de A , vá até a raiz e armazene cada nó visitado em um hashset. Em seguida, iniciando em b , suba até encontrar um nó que está contido no hashset.

Eu sei que os dois primeiros passos do algoritmo são ambos O (n) , onde N corresponde ao número de nós na árvore. No entanto, eu não tenho certeza sobre o último passo.

LCA (A, B) SubRoutine tem uma complexidade linear. Mas quantos nós, no pior cenário, podem ser encontrados na etapa 2?.

Intuitivamente, eu argumentaria que tem que ser muito menos que n nós.

Answer 1

Como @rick Decker explicado, você poderia ter $ n / 2 $ folhas na profundidade máxima em um caso. Neste caso, a etapa 3 é $ o (n \ log n) $ . este post mostra o pior caso. Considere uma árvore $ t $ consiste em uma cadeia de $ n / 2 $ nós onde o restante $ n / 2 $ nós é anexado como uma árvore equilibrada na parte inferior da corrente. Isso dá a cada profundidade de folha $ n / 2 + \ log_2 (n)=theta (n) $ com $ n / 4 $ folhas em profundidade $ \ theta (n) $ temos $ \ theta (n ^ 2) $ tempo de execução para o passo 3 neste caso. Isso é assintoticamente o pior caso desde que temos $ n $ nós na profundidade máxima $ n $ .

Há uma maneira melhor de fazer isso. Permite definir uma função $ F $

$ f (v)=begin {casos} v & \ text {if} \ quad \ texttt {aleather} (v.left)=texttt {alture} (v.right) \\ f (v.left) & \ text {se} \ quad \ texttt {alture} (v.left)> \ texttt {alture} (v.right) \\ f (v.right) & \ text {se} \ quad \ texttt {alture} (v.left) <\ texttt {alture} (v.right) \ fim {casos} $

Se as alturas das crianças de um nó $ v $ são os mesmos, então claramente $ v $ é a LCA dos nós mais profundos da subárvore enraizada na $ v $ . Se a subárvore esquerda for mais alta, queremos a LCA dos nós mais profundos da subárvore enraizada na $ v.left $ , já que são mais profundos que os nós mais profundos A subárvore enraizada na $ v.right $ . A mesma lógica segue para $ v.right $ quando é mais alto.

Os valores para $ \ texttt {alture} $ e $ f (v) $ pode ser calculado em uma travessia pós-ordem de $ t $ no tempo linear.

chamando $ f (raiz) $ deve retornar o LCA dos nós mais profundos da árvore.

Answer 2

Bem, eu não sei o que você pretende "muito menos que", mas é claro que você poderia ter sobre $ n / 2 $ Folhas na máxima profundidade: Pegue uma árvore binária completa, por exemplo, com o nível mais baixo completo.

Answer 3

Eu escreveria uma função que para cada árvore calcula o menor ancestral comum de todos os nós mais profundos, e a altura da árvore.Isso é bem simples:

Se a raiz R não tiver filial esquerda ou direita, a altura é 1 e o ancestral comum é R. Se a raiz r tiver um ramo esquerdo ou direito, calcular a altura e o menor ancestral comum daquele ramo, eA altura com raiz r é mais alta, mas o menor ancestral comum é o mesmo.

Se houver uma ramificação esquerda e , calcular a altura e menor ancestral comum de ambos os ramos.Se as alturas forem diferentes, retornamos (Altura + 1) mais o menor ancestral desse ramo.Se as alturas forem as mesmas, retornamos (altura + 1) e r como o menor ancestral comum.

Isso deve tomar as etapas do CN com uma pequena constante C se o número de nós é N. e, uma vez que devemos visitar todos os nó n (pelo menos para saber que não tem filiais), isso não pode ser melhorado.