PRG29003: Etapa 2: Projeto de estruturas de dados
Desde o início do semestre foi usada a biblioteca STL, que contém implementações das estruturas de dados estudadas. Na primeira etapa da disciplina se enfatizou conhecer e usar essas estruturas de dados. Na segunda etapa o foco está no projeto de uma estrutura de dados, e o resultado esperado é a criação de estruturas de dados pelas equipes. Podem ser criadas versões que reproduzam (possivelmente com um toque pessoal) as características das estruturas de dados estudadas, ou mesmo novas estruturas de dados, diferentes daquelas conhecidas.
As estruturas de dados que já conhecemos são:
- Lineares: filas, pilhas e listas
- Associativas: tabelas hash, conjuntos e árvores de pesquisa binária
Algumas dessas estruturas são bastante simples, e não serviriam como objeto de estudo nesta etapa da disciplina (refiro-me especificamente a filas e pilhas). As demais têm complexidade adequada para serem bem entendidas e desenvolvidas neste último mês de aula. Além delas, outras estruturas de dados podem ser escolhidas:
- Trie: uma trie é um tipo de árvore n-ária (que pode ter um número n de ramos por nodo), em que os dados estão armazenados nos ramos, e não nos nodos. Esse tipo de árvore armazena prefixos dos dados, então são adequadas para dados formados por cadeias de elementos (ex: strings, endereços IP, sequências de bits em geral, ...). Um uso conhecido para tries é como dicionário de termos para um sistema do tipo auto-completar. Uma variação de tries é radix tree.
- Array Deques: um array deque é um tipo de fila que usa um array dinâmico (i.e. que pode ser expandido ou contraído) para armazenar dados. Ela possibilita a inserção e remoção eficiente de dados de seus extremos, e o acesso a qualquer dado pode ser feito com tempo constante (i.e. o custo de tempo computacional dessa operação é O(1)).
- Hashed Array Tree: um hashed array tree (ou HAT) é parecido com um array deque, porém sua estrutura interna faz um melhor uso de memória. Apesar do nome, ela nada tem a ver com tabelas hash.
- Lista desenrolada: uma lista desenrolada é parecida com uma lista usual, porém ela possibilita armazenar múltiplos dados em cada nodo da lista. Isso traz algumas vantagens quanto ao uso de memória e localização dos dados.
- Filtros Bloom: um filtro Bloom serve para informar sobre a existência ou não de um dado, porém probabilisticamente. Ele pode resultar em falsos positivos, quando retorna verdadeiro para um dado inexistente ou desconhecido, mas nunca retorna falsos negativos. Assim, se um filtro informa que um dado é desconhecido ou inexistente, com certeza isso é verdade. Essa estrutura de dados possui várias aplicações importantes.
- ... e possivelmente outras !!!