O menor ancestral comum entre dois nós de uma BST n_{1} e n_{2} é o ascendente de n_{1} e n_{2} que está mais próximo deles. Faça um algoritmo que encontre o menor ancestral comum de dois nós de uma BST e analise o tempo de seu algoritmo. Considere que os valores n_{1} e n_{2} pertencem à BST.

Passo 1

O enunciado pede um algoritmo para encontrar o menor ancestral comum (LCA, do inglês “lowest common ancestor”) de dois nós de valores n_{1} e n_{2} em uma árvore de busca binária (BST). Vamos usar a propriedade fundamental de BST — todos os valores à esquerda de um nó são menores que o valor do nó e todos os valores à direita são maiores — para guiar a busca pelo LCA.

Passo 2

A ideia é percorrer a árvore a partir da raiz e, em cada nó T com valor \,T.\text{val}:
  • se n_{1} e n_{2} são ambos menores que T.\text{val}, então o LCA está no ramo esquerdo;
  • se n_{1} e n_{2} são ambos maiores que T.\text{val}, então o LCA está no ramo direito;
  • caso contrário (um valor de cada lado ou um igual a T.\text{val}), T é o menor ancestral comum.

Passo 3

Aqui está o pseudocódigo do algoritmo em definição recursiva:
\text{LCA}(T,n_{1},n_{2}) = \begin{cases} \varnothing, & \text{se }T = \varnothing,\\[6pt] \text{LCA}(T.\text{left},n_{1},n_{2}), & \text{se }n_{1} < T.\text{val}\text{ e }n_{2} < T.\text{val},\\[6pt] \text{LCA}(T.\text{right},n_{1},n_{2}), & \text{se }n_{1} > T.\text{val}\text{ e }n_{2} > T.\text{val},\\[6pt] T, & \text{caso contrário.} \end{cases}á]

Passo 4

Análise de tempo: a cada chamada recursiva descemos um nível da árvore. Se a altura da BST é h, o algoritmo faz no máximo h comparações antes de parar.
Em média, em uma BST balanceada, h = O(\log n); no pior caso (árvore degenerada), h = O(n). Portanto, o tempo de execução é
O(h) = \begin{cases} O(\log n), & \text{árvore balanceada},\\\ O(n), & \text{pior caso}. \end{cases}á

Resposta

O algoritmo recorre da raiz seguindo à esquerda ou à direita conforme n_{1} e n_{2} serem menores ou maiores que o valor do nó, e retorna o primeiro nó em que eles ficam em lados diferentes (ou igual a um deles). O tempo de execução é O(h), onde h é a altura da árvore ( O(\log n) em média, O(n) no pior caso).

Exercícios relacionados