Centroid

Centroid

Algoritmo que encontra os dois centroides de uma árvore em $\mathcal{O}(N)$.

Definição: O centroide de uma árvore é o nodo tal que, ao ser removido, divide a árvore em subárvores com no máximo metade dos nodos da árvore original. Em outras palavras, se a árvore tem tamanho $N$, todas as subárvores geradas pela remoção do centroide têm tamanho no máximo $\frac{N}{2}$. Uma árvore pode ter até dois centróides.