Edson Takashi Matsubara | Estruturas de Dados
O desafio consistia basicamente em implementar uma tabela hash e 5 árvores AVL, dividido em 4 tarefas:
Na tarefa 1, é necessário fazer algumas adaptações na AVL, então ela é dividida em 3 sub-tarefas:
- Adaptar o código de AVL para que os nós possuam um ponteiro para o pai.
- Implementar uma lista encadeada para cada nó da árvore que armazena os registros com chaves iguais (um nó pode ter dois ou mais registros).
- Implementar a função de sucessor de um nó que consiga olhar para os ancestrais, o que permite fazer o range query.
Construa uma AVL para cada um dos seguintes campos como chave da busca: "nome", "latitude", "longitude","codigo_uf" e "ddd". Deste modo você terá que instanciar cinco AVLs, uma para cada campo. O registro armazenado deve conter a chave de busca + o código_ibge. Observe que na AVL adaptada as chaves replicadas são armazenadas um mesmo nó. Por exemplo todas as cidades com DDD 67 serão amazenadas em um mesmo nó.
Considere as seguintes três queries: (1) cidades com latitude > 50, (2) 20 <longitude < 30 e (3) DDD == 67. Cada query irá retornar um conjunto de códigos ibge. A combinação consiste em fazer a intersecção desses conjuntos.
Faça uma interface para que seja possível fazer range queries e combinação de range queries com qualquer um dos cinco campos definidos na tarefa 2. A busca deve retornar todos do campos das cidades fornecidas na base de dados. Para a busca das cidades pelo código IBGE você deve utilizar uma tabela hash.
- Tarefa 1 - AVL adapatada com ponteiro para o pai, lista encadeada e função de sucessor
- Tarefa 2 - Construção das 5 AVLs e inserção dos registros
- Tarefa 3 - Possibilidade de fazer range queries e combinação de range queries com os campos "nome", "latitude", "longitude", "codigo_uf" e "ddd"
- Tarefa 4 - Interface funcional para realizar as buscas e uso de tabela hash para pegar as informações da cidade pelo código IBGE
Para compilar e executar o programa, execute o comando abaixo:
./run.sh