Construção de árvores

Instruções

Refatore um algoritmo de construção de árvore.

Alguns fóruns da web têm um layout de árvore, então os posts são apresentados como uma árvore. No entanto, os posts normalmente ficam armazenados em um banco de dados como um conjunto não ordenado de registros. Assim, ao apresentar os posts ao usuário, a estrutura de árvore precisa ser reconstruída.

Sua tarefa será refatorar um trecho de código que funciona, mas é lento e feio, e que implementa a lógica de construção de árvore para registros altamente abstraídos. Os registros contêm apenas um número de ID e um número de ID do pai. O número de ID está sempre entre 0 (inclusive) e o comprimento da lista de registros (exclusive). Todos os registros têm um ID do pai menor que o próprio ID, exceto o registro raiz, cujo ID do pai é igual ao próprio ID.

Um exemplo de árvore:

root (ID: 0, parent ID: 0)
|-- child1 (ID: 1, parent ID: 0)
|    |-- grandchild1 (ID: 2, parent ID: 1)
|    +-- grandchild2 (ID: 4, parent ID: 1)
+-- child2 (ID: 3, parent ID: 0)
|    +-- grandchild3 (ID: 6, parent ID: 3)
+-- child3 (ID: 5, parent ID: 0)

Comparação de desempenho

Se você quiser comparar o desempenho da sua solução com a solução com que começou, vá até o diretório benchmark e rode dotnet run.