TreeSet em Java

Java fornece um vasto conjunto de estruturas de dados para trabalhar eficientemente com coleções de elementos. Uma dessas estruturas de dados é TreeSet, uma implementação de uma árvore vermelha e preta em Java. TreeSet mantém uma ordem classificada para armazenar elementos exclusivos. Iniciantes podem achar o uso da classe Java TreeSet um pouco desafiador inicialmente. Neste artigo, vamos descobrir como usar TreeSet , explicando seus conceitos básicos e fornecendo exemplos de código para ajudá-lo a começar a incorporar TreeSet em seus projetos Java.

Estrutura TreeSet: árvore Vermelho-Preta

Como mencionamos antes, a estrutura de classes Java TreeSet é implementada como uma árvore de pesquisa binária com autoequilíbrio conhecida como árvore Red-Black. Vamos explicar o que é isso... Uma Árvore Vermelho-Preta representa uma estrutura de dados de pesquisa binária balanceada comumente empregada para armazenar e organizar dados classificados. Seu nome deriva das propriedades que mantêm seu equilíbrio:

• Cada nó da árvore é vermelho ou preto.
• A raiz da árvore Rubro-Negra é sempre preta.
• Todos os nós folha (nós NIL ou links nulos) são pretos.
• Se um nó da árvore for vermelho, então seus filhos serão pretos.
• Cada caminho simples de um nó até seus nós descendentes contém um número igual de nós pretos.

As árvores rubro-negras apresentam desempenho eficiente para operações de inserção, exclusão e pesquisa de elementos, garantindo equilíbrio. Isso garante que a altura da árvore permaneça proporcional ao logaritmo do número de nós que ela contém, resultando em complexidade de tempo logarítmica para as operações. As árvores rubro-negras encontram amplas aplicações em vários domínios, incluindo a implementação de árvores de busca balanceadas em linguagens de programação, bancos de dados (por exemplo, estruturas de índice interno) e outros cenários onde são necessários armazenamento e operações eficientes em dados classificados.

Recursos e pontos fracos do TreeSet

TreeSet fornece vários recursos importantes que o tornam uma ferramenta valiosa para gerenciar coleções de objetos de maneira ordenada. Vantagens:

• Manutenção automática de elementos em ordem de classificação. Ao adicionar ou remover elementos, a estrutura em árvore se ajusta para mantê-los ordenados. Isto elimina a necessidade de classificação manual e proporciona acesso eficiente em ordem crescente ou decrescente.
• Operações eficientes de pesquisa, inserção e exclusão. Ele utiliza uma estrutura de árvore de busca binária, permitindo essas operações com uma complexidade de tempo de O(log N) . Aqui N é o número de elementos.
• TreeSet garante a exclusividade dos elementos utilizando sua ordem natural ou um Comparator personalizado . Isto é útil ao trabalhar com coleções que requerem elementos distintos.

Limitações:

• Um pouco mais lento que o HashSet devido à manutenção da ordem de classificação.
• Não permite elementos nulos, pois depende de ordenação natural ou de um Comparador personalizado para comparação de elementos.

Java TreeSet: exemplo de operações principais

Agora vamos demonstrar como criar um TreeSet em Java, obter o tamanho da coleção, adicionar elementos nela, removê-los e verificar se um elemento está no TreeSet . Estes exemplos de código demonstram as principais operações ao trabalhar com TreeSet : criar uma instância, adicionar elementos, remover elementos, verificar a presença do elemento e obter o tamanho do TreeSet . Criando uma instância TreeSet e adicionando elementos:

// Creating a TreeSet of Integer type
TreeSet<Integer> numbers = new TreeSet<>();

// Adding elements to the TreeSet
numbers.add(18);
numbers.add(2);
numbers.add(7);
numbers.add(28);

System.out.println(numbers); // Output: [2, 7, 18, 28]

Aqui usamos o método add() para adicionar 4 números em nosso TreeSet . Se criarmos um método principal e executarmos o programa, a saída estará na ordem de classificação (2, 7, 18, 28). Removendo elementos de TreeSet :

TreeSet<String> names = new TreeSet<>();

names.add("Johnny");
names.add("Ivy");
names.add("David");
names.add("Ricky");

// Removing an element from the TreeSet
names.remove("David");

System.out.println(names); // Output: [Ivy, Johnny, Ricky]

Verificando a presença de um elemento em TreeSet :

TreeSet<String> musicalInstrument = new TreeSet<>();

musicalInstrument.add("Piano");
musicalInstrument.add("Drums");
musicalInstrumentfruits.add("Violin");
musicalInstrument.add("Double Bass");

// Checking if an element exists in the TreeSet
boolean containsPiano = musicalInstrument.contains("Piano");
boolean containsCello = musicalInstrument.contains("Cello");

System.out.println(containsPiano); // Output: true
System.out.println(containsCello); // Output: false

Obtendo o tamanho de TreeSet :

TreeSet<Character> letters = new TreeSet<>();

letters.add('A');
letters.add('B');
letters.add('C');
letters.add('D');

// Getting the size of the TreeSet
int size = letters.size();

System.out.println(size); // Output: 4

Classificando e iterando em TreeSet

TreeSet em Java fornece recursos poderosos para classificar e iterar coleções de elementos. Nesta seção, exploraremos várias técnicas para classificar elementos, iterar sobre TreeSet e realizar pesquisas baseadas em intervalo usando os métodos subSet() , headSet() e tailSet() . Por padrão, TreeSet mantém automaticamente os elementos em ordem de classificação. No entanto, podemos personalizar o comportamento de classificação fornecendo um Comparator durante a criação do TreeSet . Vejamos um exemplo:

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetSortingExample {
  public static void main(String[] args) {
    // Create a TreeSet with custom sorting
    TreeSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());

    // Add elements to the TreeSet
    numbers.add(5);
    numbers.add(3);
    numbers.add(7);
    numbers.add(1);

    System.out.println(numbers); // Output: [7, 5, 3, 1]
  }
}

No código acima, criamos um TreeSet do tipo Integer e fornecemos um Comparator personalizado usando Comparator.reverseOrder() para classificar os elementos em ordem decrescente. O TreeSet resultante conterá elementos [7, 5, 3, 1] . Existem várias maneiras de iterar TreeSet . Podemos usar um iterador ou utilizar o loop for-each aprimorado . Vejamos exemplos de ambas as abordagens:

import java.util.TreeSet;
import java.util.Iterator;

public class TreeSetIterationExample {
  public static void main(String[] args) {
    TreeSet<String> names = new TreeSet<>();

    names.add("Johnny");
    names.add("Ivy");
    names.add("Ricky");
    names.add("David");

    // Iterating using an iterator
    Iterator<String> iterator = names.iterator();
    while (iterator.hasNext()) {
      String name = iterator.next();
      System.out.println(name);
    }

    // Iterating using the enhanced for-each loop
    for (String name : names) {
      System.out.println(name);
    }
  }
}

No código acima, criamos um TreeSet chamado nomes e adicionamos alguns elementos. Em seguida, demonstramos duas maneiras de iterar sobre o TreeSet : usando um iterador e utilizando o loop for-each aprimorado. TreeSet fornece métodos para realizar pesquisas baseadas em intervalos, permitindo recuperar subconjuntos de elementos com base em critérios específicos. Os três métodos principais para pesquisas baseadas em intervalo são:

• subSet(E fromElement, E toElement) : Retorna um subconjunto de elementos de fromElement (inclusivo) para toElement (exclusivo).
• headSet(E toElement) : Retorna um subconjunto de elementos menor que toElement .
• tailSet(E fromElement) : Retorna um subconjunto de elementos maior ou igual a fromElement .

Vejamos um exemplo:

import java.util.TreeSet;

public class TreeSetRangeSearchExample {
  public static void main(String[] args) {
    TreeSet<Integer> numbers = new TreeSet<>();

    numbers.add(1);
    numbers.add(3);
    numbers.add(5);
    numbers.add(7);
    numbers.add(9);

    // Performing range-based search using subSet()
    TreeSet<Integer> subset = new TreeSet<>(numbers.subSet(3, 8));
    System.out.println(subset); // Output: [3, 5, 7]

    // Performing range-based search using headSet()
    TreeSet<Integer> headSet = new TreeSet<>(numbers.headSet(6));
    System.out.println(headSet); // Output: [1, 3, 5]

    // Performing range-based search using tailSet()
     TreeSet<Integer> tailSet = new TreeSet<>(numbers.tailSet(5));
    System.out.println(tailSet); // Output: [5, 7, 9]
  }
}

No código acima, criamos um TreeSet chamado numbers e adicionamos alguns elementos. Em seguida, demonstramos pesquisas baseadas em intervalo usando os métodos subSet() , headSet() e tailSet() .

• O subconjunto TreeSet contém elementos entre 3 (inclusivo) e 8 (exclusivo), que são [3, 5, 7] .
• O headSet TreeSet contém elementos menores que 6, que são [1, 3, 5] .
• O tailSet TreeSet contém elementos maiores ou iguais a 5, que são [5, 7, 9] .

Esses métodos de pesquisa baseados em intervalo nos permitem recuperar subconjuntos de elementos com base em critérios específicos, proporcionando flexibilidade no trabalho com dados classificados.

Comparador em TreeSet: classificação com critérios personalizados

Exceto pela ordem natural, você pode usar um Comparator personalizado para classificar TreeSet . Nesta seção, nos aprofundaremos no conceito de comparador e sua função no TreeSet . Exploraremos como criar um TreeSet com um comparador personalizado e forneceremos exemplos de código para demonstrar a classificação de TreeSet com base em critérios específicos.

O que é comparador?

Um Comparador é uma interface em Java que permite a classificação personalizada de objetos. Ele fornece uma maneira de definir a ordem dos elementos com base em atributos ou propriedades específicas. Ao implementar a interface Comparator e substituir seu método compare() , podemos especificar como os elementos devem ser classificados em um TreeSet .

Criando TreeSet com um comparador personalizado

Para criar um TreeSet com um comparador personalizado, precisamos fornecer o comparador como argumento ao criar a instância TreeSet . Vejamos um exemplo:

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetComparatorExample {
  public static void main(String[] args) {
    // Create a TreeSet with a custom comparator
    TreeSet<String> names = new TreeSet<>(new LengthComparator());

    // Add elements to the TreeSet
    names.add("Johnny");
    names.add("Ivy");
    names.add("Rick");
    names.add("David");

    System.out.println(names); // Output: [Ivy, Johnny, David, Rick]
  }
}

class LengthComparator implements Comparator<String> {
  @Override
  public int compare(String s1, String s2) {
    return Integer.compare(s1.length(), s2.length());
  }
}

No código acima, criamos um TreeSet chamado nomes com um comparador personalizado chamado LengthComparator . O LengthComparator compara o comprimento de duas strings e as classifica de acordo. Como resultado, o TreeSet é classificado com base no comprimento das strings, fornecendo a saída [Ivy, Rick, David, Johnny] .

Exemplos de classificação de TreeSet usando um comparador

Além de criar um TreeSet com um comparador personalizado, também podemos usar um comparador para classificar um TreeSet temporariamente sem modificar sua ordem natural. Vejamos um exemplo:

import java.util.Comparator;
import java.util.TreeSet;

  public class TreeSetTest {
    public static void main(String[] args) {
      TreeSet<String> names = new TreeSet<>();

      names.add("Johnny");
      names.add("Ivy");
      names.add("Ricky");
      names.add("David");

      // Sort TreeSet temporarily using a comparator
      TreeSet<String> sortedNames = new TreeSet<>(Comparator.reverseOrder());
      sortedNames.addAll(names);

      System.out.println(sortedNames); // Output: [Ricky, Johnny, Ivy, David]
      System.out.println(names); // Output: [David, Ivy, Johnny, Ricky]
    }
  }

No código acima, criamos um TreeSet chamado nomes e adicionamos alguns elementos. Em seguida, criamos um novo TreeSet chamado sortedNames com um comparador personalizado Comparator.reverseOrder() . Ao adicionar todos os elementos dos nomes originais TreeSet ao sortedNames , obtemos uma versão classificada temporária do TreeSet .

Comparando TreeSet com outras estruturas de dados

Comparando TreeSet com HashSet

Tanto TreeSet quanto HashSet são implementações da interface Set em Java. No entanto, existem diferenças significativas entre eles. TreeSet : TreeSet armazena elementos exclusivos em ordem de classificação. Ele usa uma árvore de pesquisa binária com autoequilíbrio (geralmente uma árvore vermelha e preta) para manter a ordem de classificação, resultando em complexidade de tempo logarítmica para operações como inserção, exclusão e pesquisa. TreeSet é eficiente para manter uma coleção classificada e executar operações baseadas em intervalo. Porém, possui maior sobrecarga de memória devido à estrutura em árvore e não permite elementos nulos. HashSet : HashSet armazena elementos únicos de maneira não ordenada usando códigos hash e tabela hash internamente. Ele fornece complexidade de tempo constante para operações básicas como inserção, exclusão e pesquisa. HashSet é eficiente para pesquisa rápida de elementos e não impõe nenhuma sobrecarga de memória adicional para manter a ordem. No entanto, não garante qualquer ordenação específica dos elementos.

Quando usar TreeSet:

• Quando você precisa manter os elementos em uma ordem de classificação automaticamente.
• Quando você precisa de operações baseadas em intervalo ou precisa encontrar elementos dentro de um intervalo específico de forma eficiente.
• Quando elementos duplicados não são permitidos e a exclusividade é essencial.
• Quando você deseja trocar um uso de memória um pouco maior pelos benefícios da classificação automática e das operações de intervalo.

Comparando TreeSet com ArrayList

ArrayList é uma implementação de array dinâmico em Java. Aqui estão as principais diferenças entre TreeSet e ArrayList :

• TreeSet : TreeSet armazena elementos exclusivos em ordem classificada, fornecendo operações eficientes para manter uma coleção classificada e realizar pesquisas baseadas em intervalo. Possui complexidade de tempo logarítmica para operações. TreeSet não é adequado para acesso aleatório ou manutenção da ordem de inserção.
• ArrayList : ArrayList armazena elementos na ordem de inserção, fornecendo acesso aleatório rápido aos elementos usando índices. Possui complexidade de tempo constante para a maioria das operações ao acessar elementos por índice. Porém, possui complexidade de tempo linear para inserir ou remover elementos do meio da lista, pois requer deslocamento de elementos.

Quando considerar outras estruturas de dados

• Se a manutenção de elementos em uma ordem classificada não for necessária e você precisar de uma pesquisa rápida de elementos ou de uma coleção não ordenada, HashSet pode ser uma escolha melhor.
• Se você precisar de acesso aleatório frequente aos elementos por índice ou precisar manter a ordem de inserção, ArrayList seria mais adequado.