Link-cut trees e aplicações em estruturas de dados retroativas (2022)
- Authors:
- USP affiliated author: NORONHA, FELIPE CASTRO DE - IME
- School: IME
- Subjects: ESTRUTURAS DE DADOS; TEORIA DA COMPUTAÇÃO
- Language: Português
- Abstract: Estruturas de dados retroativas permitem a realização de operações que afetam não somente o estado atual da estrutura, mas também qualquer um de seus estados passados. Além disso, uma link-cut tree é uma estrutura de dados que permite a manutenção de uma floresta de árvores enraizadas com peso nas arestas, e onde os nós de cada árvore possuem um número arbitrário de filhos. Tal estrutura é muito utilizada como base para o desenvolvimento de estruturas de dados retroativas, e neste trabalho estudaremos as versões retroativas dos problemas de union-find e floresta geradora mínima. Para isso, implementamos essas estruturas em C++ e descrevemos as ideias por trás de seus funcionamentos. Ademais, apresentamos uma melhoria da solução originalmente apresentada para a floresta geradora mínima retroativa, que retira limitações sem piorar sua performance.
- Imprenta:
-
ABNT
NORONHA, Felipe Castro de. Link-cut trees e aplicações em estruturas de dados retroativas. 2022. Trabalho de Conclusão de Curso (Graduação) – Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, 2022. Disponível em: https://bdta.abcd.usp.br/directbitstream/2fbf453b-b7db-4f95-a805-e41dc8eb7b0f/3122356.pdf. Acesso em: 28 abr. 2024. -
APA
Noronha, F. C. de. (2022). Link-cut trees e aplicações em estruturas de dados retroativas (Trabalho de Conclusão de Curso (Graduação). Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo. Recuperado de https://bdta.abcd.usp.br/directbitstream/2fbf453b-b7db-4f95-a805-e41dc8eb7b0f/3122356.pdf -
NLM
Noronha FC de. Link-cut trees e aplicações em estruturas de dados retroativas [Internet]. 2022 ;[citado 2024 abr. 28 ] Available from: https://bdta.abcd.usp.br/directbitstream/2fbf453b-b7db-4f95-a805-e41dc8eb7b0f/3122356.pdf -
Vancouver
Noronha FC de. Link-cut trees e aplicações em estruturas de dados retroativas [Internet]. 2022 ;[citado 2024 abr. 28 ] Available from: https://bdta.abcd.usp.br/directbitstream/2fbf453b-b7db-4f95-a805-e41dc8eb7b0f/3122356.pdf
Download do texto completo
| Tipo | Nome | Link | |
|---|---|---|---|
 |
3122356.pdf | Direct link |
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
