Zestaw drzew w Javie

Java zapewnia szeroki zestaw struktur danych umożliwiających efektywną pracę z kolekcjami elementów. Jedną z takich struktur danych jest TreeSet, implementacja czerwono-czarnego drzewa w Javie. TreeSet utrzymuje posortowany porządek przechowywania unikalnych elementów. Początkującym korzystanie z klasy Java TreeSet może początkowo wydawać się nieco trudne. W tym artykule dowiemy się, jak używać TreeSet , wyjaśniając jego podstawowe koncepcje i podając przykłady kodu, które pomogą Ci zacząć włączać TreeSet do swoich projektów Java.

Struktura TreeSet: czerwono-czarne drzewo

Jak wspomnieliśmy wcześniej, struktura klas Java TreeSet jest zaimplementowana jako samobalansujące drzewo wyszukiwania binarnego, znane jako drzewo czerwono-czarne. Wyjaśnijmy, co to jest... Czerwono-czarne drzewo reprezentuje zrównoważoną strukturę danych wyszukiwania binarnego, powszechnie stosowaną do przechowywania i organizowania posortowanych danych. Swoją nazwę wywodzi od właściwości utrzymujących równowagę:

Każdy węzeł w drzewie jest czerwony lub czarny.
Korzeń czerwono-czarnego drzewa jest zawsze czarny.
Wszystkie węzły liściowe (węzły NIL lub łącza zerowe) są czarne.
Jeśli węzeł drzewa jest czerwony, to jego dzieci są czarne.
Każda prosta ścieżka od węzła do węzłów potomnych zawiera taką samą liczbę czarnych węzłów.

Drzewa czerwono-czarne charakteryzują się wydajną wydajnością podczas operacji wstawiania, usuwania i wyszukiwania elementów, zapewniając równowagę. Gwarantuje to, że wysokość drzewa pozostaje proporcjonalna do logarytmu liczby zawartych w nim węzłów, co skutkuje logarytmiczną złożonością czasową operacji. Drzewa czerwono-czarne znajdują szerokie zastosowanie w różnych dziedzinach, w tym we wdrażaniu zrównoważonych drzew wyszukiwania w językach programowania, bazach danych (np. Wewnętrznych strukturach indeksów) i innych scenariuszach, w których konieczne jest wydajne przechowywanie i operacje na posortowanych danych.

Cechy i słabości TreeSet

TreeSet zapewnia kilka kluczowych funkcji, które czynią go cennym narzędziem do zarządzania kolekcjami obiektów w sposób posortowany. Zalety:

Automatyczne utrzymanie elementów w posortowanej kolejności. Podczas dodawania lub usuwania elementów struktura drzewa dostosowuje się, aby je posortować. Eliminuje to potrzebę ręcznego sortowania i zapewnia efektywny dostęp w kolejności rosnącej lub malejącej.
Wydajne operacje wyszukiwania, wstawiania i usuwania. Wykorzystuje strukturę drzewa wyszukiwania binarnego, umożliwiając wykonywanie tych operacji ze złożonością czasową O(log N) . Tutaj N jest liczbą elementów.
TreeSet gwarantuje niepowtarzalność elementów wykorzystując ich naturalne uporządkowanie lub niestandardowy Komparator . Jest to przydatne podczas pracy z kolekcjami wymagającymi odrębnych elementów.

Ograniczenia:

Nieco wolniejszy niż HashSet ze względu na utrzymanie posortowanej kolejności.
Nie zezwala na elementy zerowe, ponieważ opiera się na naturalnym uporządkowaniu lub niestandardowym komparatorze do porównywania elementów.

Java TreeSet: przykład głównych operacji

Teraz zademonstrujemy, jak utworzyć TreeSet w Javie, uzyskać rozmiar kolekcji, dodać do niej elementy, usunąć je i sprawdzić, czy element znajduje się w TreeSet . Te przykłady kodu demonstrują główne operacje podczas pracy z TreeSet : tworzenie instancji, dodawanie elementów, usuwanie elementów, sprawdzanie obecności elementów i uzyskiwanie rozmiaru TreeSet . Tworzenie instancji TreeSet i dodawanie elementów:

// 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]

Tutaj używamy metody add() , aby dodać 4 liczby w naszym TreeSet . Jeśli utworzymy metodę główną i uruchomimy program, dane wyjściowe będą posortowane (2, 7, 18, 28). Usuwanie elementów z 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]

Sprawdzanie obecności elementu w 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

Uzyskanie rozmiaru 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

Sortowanie i iteracja w TreeSet

TreeSet w Javie zapewnia zaawansowane funkcje sortowania i iteracji po kolekcjach elementów. W tej sekcji omówimy różne techniki sortowania elementów, iterację po TreeSet i przeprowadzanie wyszukiwania w oparciu o zakres przy użyciu metod subSet() , headSet() i tailSet() . Domyślnie TreeSet automatycznie utrzymuje elementy w posortowanej kolejności. Możemy jednak dostosować zachowanie sortowania, udostępniając komparator podczas tworzenia TreeSet . Zobaczmy przykład:

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]
  }
}

W powyższym kodzie tworzymy TreeSet typu Integer i udostępniamy niestandardowy komparator za pomocą metody Comparator.reverseOrder() w celu sortowania elementów w kolejności malejącej. Wynikowy TreeSet będzie zawierał elementy [7, 5, 3, 1] . Istnieje wiele sposobów iteracji po TreeSet . Możemy użyć iteratora lub skorzystać z ulepszonej pętli for-each . Zobaczmy przykłady obu podejść:

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);
    }
  }
}

W powyższym kodzie tworzymy TreeSet o nazwie Names i dodajemy kilka elementów. Następnie zademonstrujemy dwa sposoby iteracji po zestawie TreeSet : użycie iteratora i wykorzystanie ulepszonej pętli for-each. TreeSet zapewnia metody wyszukiwania w oparciu o zakres, co pozwala nam pobierać podzbiory elementów w oparciu o określone kryteria. Trzy główne metody wyszukiwania opartego na zakresie to:

subSet(E fromElement, E toElement) : Zwraca podzbiór elementów od fromElement (włącznie) do toElement (wyłącznie).
headSet(E toElement) : Zwraca podzbiór elementów mniejszy niż toElement .
tailSet(E fromElement) : Zwraca podzbiór elementów większy lub równy fromElement .

Zobaczmy przykład:

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]
  }
}

W powyższym kodzie tworzymy TreeSet o nazwie Numbers i dodajemy kilka elementów. Następnie zademonstrujemy wyszukiwanie oparte na zakresach przy użyciu metod subSet() , headSet() i tailSet() .

Podzbiór TreeSet zawiera elementy od 3 (włącznie) do 8 (wyłącznie), którymi są [ 3 , 5, 7] .
HeadSet TreeSet zawiera elementy mniejsze niż 6, czyli [1, 3, 5 ] .
TailSet TreeSet zawiera elementy większe lub równe 5, którymi są [ 5, 7, 9] .

Te metody wyszukiwania oparte na zakresach pozwalają nam wyszukiwać podzbiory elementów w oparciu o określone kryteria, zapewniając elastyczność w pracy z posortowanymi danymi.

Komparator w TreeSet: Sortowanie według kryteriów niestandardowych

Z wyjątkiem porządku naturalnego, możesz użyć niestandardowego komparatora do sortowania TreeSet . W tej sekcji zagłębimy się w koncepcję komparatora i jego rolę w TreeSet . Zbadamy, jak utworzyć TreeSet za pomocą niestandardowego komparatora i podamy przykłady kodu, aby zademonstrować sortowanie TreeSet w oparciu o określone kryteria.

Co to jest komparator?

Komparator to interfejs w Javie, który umożliwia niestandardowe sortowanie obiektów . Umożliwia zdefiniowanie kolejności elementów w oparciu o określone atrybuty lub właściwości. Implementując interfejs Comparator i zastępując jego metodę Compare() , możemy określić, w jaki sposób elementy powinny być sortowane w TreeSet .

Tworzenie TreeSet z niestandardowym komparatorem

Aby utworzyć TreeSet z niestandardowym komparatorem, musimy podać komparator jako argument podczas tworzenia instancji TreeSet . Zobaczmy przykład:

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());
  }
}

W powyższym kodzie tworzymy TreeSet o nazwie names z niestandardowym komparatorem o nazwie LenghtComparator . DistanceComparator porównuje długość dwóch ciągów i odpowiednio je sortuje. W rezultacie TreeSet jest sortowany na podstawie długości ciągów znaków, co daje wynik [Ivy, Rick, David, Johnny] .

Przykłady sortowania TreeSet przy użyciu komparatora

Oprócz tworzenia TreeSet za pomocą niestandardowego komparatora, możemy również użyć komparatora do tymczasowego sortowania TreeSet bez modyfikowania jego naturalnego porządku. Zobaczmy przykład:

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]
    }
  }

W powyższym kodzie tworzymy TreeSet o nazwie Names i dodajemy kilka elementów. Następnie tworzymy nowy zestaw drzew o nazwie sortedNames z niestandardowym komparatorem Comparator.reverseOrder() . Dodając wszystkie elementy z oryginalnych nazw TreeSet do sortedNames , otrzymujemy tymczasową posortowaną wersję TreeSet .

Porównanie TreeSet z innymi strukturami danych

Porównanie TreeSet z HashSet

Zarówno TreeSet , jak i HashSet są implementacjami interfejsu Set w Javie. Istnieją jednak między nimi znaczne różnice. TreeSet : TreeSet przechowuje unikalne elementy w posortowanej kolejności. Wykorzystuje samorównoważące się drzewo wyszukiwania binarnego (zwykle drzewo czerwono-czarne), aby zachować posortowany porządek, co skutkuje logarytmiczną złożonością czasową dla operacji takich jak wstawianie, usuwanie i wyszukiwanie. TreeSet jest wydajny w utrzymywaniu posortowanej kolekcji i wykonywaniu operacji opartych na zakresach. Jednakże ma większe obciążenie pamięci ze względu na strukturę drzewa i nie pozwala na elementy zerowe. HashSet : HashSet przechowuje unikalne elementy w sposób nieuporządkowany, używając wewnętrznie kodów skrótu i tablicy haszującej. Zapewnia stałą złożoność czasową dla podstawowych operacji, takich jak wstawianie, usuwanie i wyszukiwanie. HashSet jest wydajny w przypadku szybkiego wyszukiwania elementów i nie wymaga dodatkowego obciążenia pamięci w celu utrzymania porządku. Nie gwarantuje jednak określonego uporządkowania elementów.

Kiedy używać TreeSet:

Gdy chcesz automatycznie zachować posortowaną kolejność elementów.
Gdy potrzebujesz operacji opartych na zakresach lub chcesz efektywnie znaleźć elementy w określonym zakresie.
Kiedy duplikaty elementów są niedozwolone i niepowtarzalność jest niezbędna.
Kiedy chcesz zamienić nieco większe zużycie pamięci na korzyści płynące z automatycznego sortowania i operacji na zakresie.

Porównanie TreeSet z ArrayList

ArrayList to dynamiczna implementacja tablic w Javie. Oto kluczowe różnice między TreeSet i ArrayList :

TreeSet : TreeSet przechowuje unikalne elementy w posortowanej kolejności, zapewniając wydajne operacje utrzymywania posortowanej kolekcji i przeprowadzania wyszukiwań w oparciu o zakres. Ma logarytmiczną złożoność czasową dla operacji. TreeSet nie nadaje się do dostępu losowego ani utrzymywania kolejności wstawiania.
ArrayList : ArrayList przechowuje elementy w kolejności wstawiania, zapewniając szybki losowy dostęp do elementów za pomocą indeksów. Ma stałą złożoność czasową dla większości operacji podczas uzyskiwania dostępu do elementów według indeksu. Ma jednak liniową złożoność czasową przy wstawianiu lub usuwaniu elementów ze środka listy, ponieważ wymaga przesuwania elementów.

Kiedy rozważyć inne struktury danych

Jeśli utrzymywanie elementów w posortowanej kolejności nie jest wymagane i potrzebujesz szybkiego wyszukiwania elementów lub nieuporządkowanej kolekcji, lepszym wyborem może być HashSet .
Jeśli potrzebujesz częstego losowego dostępu do elementów według indeksu lub chcesz zachować kolejność wstawiania, bardziej odpowiednia będzie ArrayList .