1. O que é TreeMap

TreeMap é uma implementação de mapa baseada em uma árvore rubro-negra (árvore de busca binária balanceada) que oferece operações com complexidade O(logN). Ao iterar sobre um TreeMap, os elementos são retornados em ordem:

• Segundo a ordem natural das chaves
• Usando um Comparator perrsonalizado para ordenação

2. Utilização Básica

public class ExemploTreeMap {
    public static void main(String[] args) {
        // Criando um TreeMap com ordenação natural das chaves
        MapaOrdenado<string string=""> dicionario = new MapaOrdenado<>();
        dicionario.adicionar("1", "valor A");
        dicionario.adicionar("3", "valor C");
        dicionario.adicionar("2", "valor B");
        dicionario.adicionar("4", "valor D");

        // Iterando sobre os elementos em ordem das chaves
        for (MapaOrdenado.Entrada<string string=""> elemento : dicionario.todosElementos()) {
            System.out.println(elemento);
        }
    }
}</string></string>

3. Aálise do Código Fonte

3.1. Estrutura da Classe

public class MapaOrdenado<k> 
    extends MapaAbstrato<k> 
    implements MapaNavegavel<k>, Cloneavel, java.io.Serializable {
    
    // Comparador para ordenação das chaves
    private final Comparador super K> comparador;
    
    // Raiz da árvore rubro-negra
    private transient No<k> raiz;
    
    // Número de elementos na árvore
    private transient int tamanho = 0;
    
    // Contador de modificações
    private transient int contadorModificacoes = 0;
    
    // Construtor padrão - usa ordenação natural das chaves
    public MapaOrdenado() {
        comparador = null;
    }
    
    // Construtor com comparador personalizado
    public MapaOrdenado(Comparador super K> comparador) {
        this.comparador = comparador;
    }
}</k></k></k></k>

3.2. Método de Inserção (adicionar)

public V adicionar(K chave, V valor) {
    No<k> noAtual = raiz;
    
    // Se a árvore estiver vazia, cria o primeiro nó
    if (noAtual == null) {
        comparar(chave, chave); // Verificação de tipo (e possivelmente nulo)
        
        raiz = new No<>(chave, valor, null);
        tamanho = 1;
        contadorModificacoes++;
        return null;
    }
    
    int cmp;
    No<k> noPai;
    
    // Determina qual método de comparação usar
    Comparador super K> cmpComparador = comparador;
    
    // Usando comparador personalizado
    if (cmpComparador != null) {
        do {
            noPai = noAtual;
            cmp = cmpComparador.comparar(chave, noAtual.chave);
            
            // Se a chave for menor, vai para a subárvore esquerda
            if (cmp < 0)
                noAtual = noAtual.esquerda;
            // Se a chave for maior, vai para a subárvore direita
            else if (cmp > 0)
                noAtual = noAtual.direita;
            // Se a chave já existe, atualiza o valor
            else
                return noAtual.definirValor(valor);
        } while (noAtual != null);
    } 
    // Usando ordenação natural (Comparable)
    else {
        if (chave == null)
            throw new NullPointerException();
        
        @SuppressWarnings("unchecked")
        Comparavel super K> k = (Comparavel super K>) chave;
        
        do {
            noPai = noAtual;
            cmp = k.compararPara(noAtual.chave);
            
            if (cmp < 0)
                noAtual = noAtual.esquerda;
            else if (cmp > 0)
                noAtual = noAtual.direita;
            else
                return noAtual.definirValor(valor);
        } while (noAtual != null);
    }
    
    // Insere o novo nó na árvore
    No<k> novoNo = new No<>(chave, valor, noPai);
    if (cmp < 0)
        noPai.esquerda = novoNo;
    else
        noPai.direita = novoNo;
    
    // Restabelece o balanceamento da árvore rubro-negra
    corrigirDepoisInsercao(novoNo);
    tamanho++;
    contadorModificacoes++;
    return null;
}</k></k></k>

3.3. Método de Busca (obter)

public V obter(Object chave) {
    No<k> no = obterNo(chave);
    return (no == null ? null : no.valor);
}

final No<k> obterNo(Object chave) {
    // Se houver comparador personalizado, usa-o
    if (comparador != null)
        return obterNoUsandoComparador(chave);
    
    if (chave == null)
        throw new NullPointerException();
    
    @SuppressWarnings("unchecked")
    Comparavel super K> k = (Comparavel super K>) chave;
    
    // Busca na árvore binária de busca
    No<k> no = raiz;
    while (no != null) {
        int cmp = k.compararPara(no.chave);
        if (cmp < 0)
            no = no.esquerda;
        else if (cmp > 0)
            no = no.direita;
        else
            return no;
    }
    return null;
}</k></k></k>

3.4. Verificação de Chavee (contemChave)

public boolean contemChave(Object chave) {
    // Simplesmente chama o método de busca
    return obterNo(chave) != null;
}

3.5. Método de Remoção (remover)

public V remover(Object chave) {
    // Localiza o nó a ser removido
    No<k> no = obterNo(chave);
    if (no == null)
        return null;
    
    V valorAntigo = no.valor;
    // Remove o nó
    excluirNo(no);
    return valorAntigo;
}

private void excluirNo(No<k> no) {
    contadorModificacoes++;
    tamanho--;
    
    // Se o nó tem ambos os filhos, encontra o sucessor
    if (no.esquerda != null && no.direita != null) {
        No<k> sucessor = sucessor(no);
        no.chave = sucessor.chave;
        no.valor = sucessor.valor;
        no = sucessor;
    } 
    
    // Determina o nó de substituição
    No<k> substituto = (no.esquerda != null ? no.esquerda : no.direita);
    
    // Se houver um nó de substituição
    if (substituto != null) {
        // Conecta o substituto ao pai
        substituto.pai = no.pai;
        if (no.pai == null)
            raiz = substituto;
        else if (no == no.pai.esquerda)
            no.pai.esquerda = substituto;
        else
            no.pai.direita = substituto;
        
        // Limpa as referências do nó excluído
        no.esquerda = no.direita = no.pai = null;
        
        // Restabelece o balanceamento da árvore rubro-negra
        if (no.cor == PRETO)
            corrigirDepoisRemocao(substituto);
    } 
    // Se o nó era a raiz (último nó na árvore)
    else if (no.pai == null) {
        raiz = null;
    } else { // Nó sem filhos
        if (no.cor == PRETO)
            // Restabelece o balanceamento
            corrigirDepoisRemocao(no);
        
        // Atualiza o ponteiro do pai
        if (no.pai != null) {
            if (no == no.pai.esquerda)
                no.pai.esquerda = null;
            else if (no == no.pai.direita)
                no.pai.direita = null;
            no.pai = null;
        }
    }
}</k></k></k></k>