Como criar regras de ordenação para pesquisa em uma estrutura TreeMap

6 de novembro de 2012 2 respostas

sk8boy 6 de novembro de 2012

Olá galera, tudo bem?

Bom seguinte, estou com um problema aqui que preciso implementar uma estrutura de dados em arvore, parecido com que ocorre no sistemas de diretorio do Unix e Windows ou com tabelas com auto-relacionamento em banco de dados.

Imaginem a estrutura de diretórios do Windows eu tenho o diretório C:\Arquivos e tbm tenho o C:\Documentos e dentro do primeiro eu tenho os seguintes diretórios C:\Arquivos\Fotos, C:\Arquivos\Programas e dentro do ultimo eu tenho o C:\Arquivos\Programas\Instaladores

Ou imaginando a ideia do auto-relacionamento em um banco de dados relacional tenho uma tabela chamada Colaborador com os seguintes campos:

Codigo (int PK)

Nome (String)

Chefe (int FK)

sendo que em um auto relacionamento eu possuo os códigos 1, 2, 11, 12 e 111, sendo que o 11 e 12 são dependentes do 1 e o 111 é dependente do 11

Preciso de uma estrutura de dados em Java em que eu possa implementar esse tipo de regra (chaves únicas com ou sem dependência de uma em forma de arvore).

Estudando um pouco o assunto verifiquei que existe a classe TreeMap da Collections Map, ela utiliza uma chave unica para armazenar cada elemento e que sua ordenação é por arvore (já é uma parte do que preciso). Verifiquei também que por default ela ordena as chaves de maneira crescente (1,2,3,4,5…) mas que você pode implementar regras para mudar o tipo de ordenação.

Minha dúvida é, como posso montar um algoritmo para que ela ordene sempre as chaves pai e suas respectivas filhas até as folhas? por exemplo:
1,11,111,12,2,3…

Ah, lembrando também que na hora de fazer a pesquisa, eu preciso saber quais são os “pais” e dependentes daquela chave, por exemplo, se eu pesquisar o 11, eu devo mostrar anterioramente a ela o 1 e após ela o 111

Desde já agradeço a ajuda

2 Respostas

Rodrigo_Sasaki 6 de nov. de 2012

Bom, você pode instanciar um TreeMap indicando o critério de comparação, através de um objeto Comparator.

Map<Integer, Integer> map = new TreeMap<Integer, Integer>(new MyTreeComparator());

E sua classe simplesmente implementa a interface Comparator.

class MyTreeComparator implements Comparator<Integer>{

    @Override
    public int compare(Integer one, Integer other){
        // Sua implementação.
    }

}

Na implementação você vai precisar comparar caractere a caractere, pois você não quer que 111 seja realmente o número 111, e sim o nível da árvore.

E tem algo a se pensar também, e se um nó tiver mais de 9 nós filhos, como ele vai comparar?

sk8boy 6 de nov. de 2012

Rodrigo Sasaki:
Bom, você pode instanciar um TreeMap indicando o critério de comparação, através de um objeto Comparator.
Map<Integer, Integer> map = new TreeMap<Integer, Integer>(new MyTreeComparator());
E sua classe simplesmente implementa a interface Comparator.
class MyTreeComparator implements Comparator<Integer>{

    @Override
    public int compare(Integer one, Integer other){
        // Sua implementação.
    }

}
Na implementação você vai precisar comparar caractere a caractere, pois você não quer que 111 seja realmente o número 111, e sim o nível da árvore.
E tem algo a se pensar também, e se um nó tiver mais de 9 nós filhos, como ele vai comparar?

Bom entendi parcialmente Rodrigo, essa Interface Comparator serve para implementar comparações é isso? Eu ainda iria ter que desenvolver o algorítimo né?

Criado 6 de novembro de 2012

Ultima resposta 6 de nov. de 2012

Respostas 2

Participantes 2

2 Respostas

Topicos relacionados