TreeSet in Java

Java bietet einen umfangreichen Satz an Datenstrukturen für die effiziente Arbeit mit Elementsammlungen. Eine solche Datenstruktur ist TreeSet, eine Implementierung eines Rot-Schwarz-Baums in Java. TreeSet verwaltet eine sortierte Reihenfolge zum Speichern eindeutiger Elemente. Anfänger können die Verwendung der Java TreeSet- Klasse zunächst als etwas herausfordernd empfinden . In diesem Artikel werden wir herausfinden, wie man TreeSet verwendet , die Kernkonzepte erläutern und Codebeispiele bereitstellen, die Ihnen bei der Integration von TreeSet in Ihre Java-Projekte helfen.

TreeSet-Struktur: Rot-Schwarzer Baum

Wie bereits erwähnt, ist die Klassenstruktur von Java TreeSet als selbstausgleichender binärer Suchbaum implementiert, der als Rot-Schwarz-Baum bekannt ist. Lassen Sie uns erklären, was das ist ... Ein Rot-Schwarz-Baum stellt eine ausgewogene binäre Suchdatenstruktur dar, die üblicherweise zum Speichern und Organisieren sortierter Daten verwendet wird. Der Name leitet sich von den Eigenschaften ab, die sein Gleichgewicht aufrechterhalten:

• Jeder Knoten im Baum ist rot oder schwarz.
• Die Wurzel des Rot-Schwarz-Baums ist immer schwarz.
• Alle Blattknoten (NIL-Knoten oder Null-Links) sind schwarz.
• Wenn ein Knoten des Baums rot ist, sind seine untergeordneten Knoten schwarz.
• Jeder einfache Pfad von einem Knoten zu seinen Nachkommenknoten enthält die gleiche Anzahl schwarzer Knoten.

Rot-Schwarz-Bäume bieten eine effiziente Leistung für Einfüge-, Lösch- und Elementsuchvorgänge, indem sie für ein Gleichgewicht sorgen. Dies garantiert, dass die Höhe des Baums proportional zum Logarithmus der Anzahl der darin enthaltenen Knoten bleibt, was zu einer logarithmischen Zeitkomplexität für Operationen führt. Rot-Schwarz-Bäume finden vielfältige Anwendungen in verschiedenen Bereichen, einschließlich der Implementierung ausgewogener Suchbäume in Programmiersprachen, Datenbanken (z. B. interne Indexstrukturen) und anderen Szenarien, in denen effiziente Speicherung und Operationen an sortierten Daten erforderlich sind.

Merkmale und Schwächen von TreeSet

TreeSet bietet mehrere wichtige Funktionen, die es zu einem wertvollen Werkzeug für die sortierte Verwaltung von Objektsammlungen machen. Vorteile:

• Automatische Pflege der Elemente in sortierter Reihenfolge. Beim Hinzufügen oder Entfernen von Elementen wird die Baumstruktur angepasst, um die Sortierung beizubehalten. Dadurch entfällt die Notwendigkeit einer manuellen Sortierung und ermöglicht einen effizienten Zugriff in auf- oder absteigender Reihenfolge.
• Effiziente Such-, Einfüge- und Löschvorgänge. Es nutzt eine binäre Suchbaumstruktur und ermöglicht diese Operationen mit einer Zeitkomplexität von O(log N) . Hier ist N die Anzahl der Elemente.
• TreeSet garantiert die Einzigartigkeit von Elementen durch die Verwendung ihrer natürlichen Reihenfolge oder eines benutzerdefinierten Comparators . Dies ist nützlich, wenn Sie mit Sammlungen arbeiten, die unterschiedliche Elemente erfordern.

Einschränkungen:

• Aufgrund der Beibehaltung der sortierten Reihenfolge etwas langsamer als HashSet .
• Erlaubt keine Nullelemente, da für den Elementvergleich eine natürliche Reihenfolge oder ein benutzerdefinierter Komparator erforderlich ist.

Java TreeSet: Beispiel für Hauptoperationen

Lassen Sie uns nun zeigen, wie Sie ein TreeSet in Java erstellen, die Größe der Sammlung ermitteln, Elemente hinzufügen, daraus entfernen und prüfen, ob sich ein Element im TreeSet befindet . Diese Codebeispiele veranschaulichen die Hauptvorgänge bei der Arbeit mit TreeSet : Erstellen einer Instanz, Hinzufügen von Elementen, Entfernen von Elementen, Überprüfen auf Elementpräsenz und Ermitteln der Größe von TreeSet . Erstellen einer TreeSet- Instanz und Hinzufügen von Elementen:

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

Hier verwenden wir die Methode add() , um 4 Zahlen in unserem TreeSet hinzuzufügen . Wenn wir eine Hauptmethode erstellen und das Programm ausführen, erfolgt die Ausgabe in sortierter Reihenfolge (2, 7, 18, 28). Elemente aus TreeSet entfernen :

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]

Überprüfen, ob ein Element in TreeSet vorhanden ist :

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

Ermitteln der Größe von 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

Sortieren und Iterieren in TreeSet

TreeSet in Java bietet leistungsstarke Funktionen zum Sortieren und Durchlaufen von Elementsammlungen. In diesem Abschnitt werden wir verschiedene Techniken zum Sortieren von Elementen, zum Durchlaufen von TreeSet und zum Durchführen bereichsbasierter Suchen mit den Methoden subSet() , headSet() und tailSet() untersuchen . Standardmäßig verwaltet TreeSet Elemente automatisch in sortierter Reihenfolge. Wir können das Sortierverhalten jedoch anpassen, indem wir während der TreeSet- Erstellung einen Comparator bereitstellen . Sehen wir uns ein Beispiel an:

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

Im obigen Code erstellen wir ein TreeSet vom Typ Integer und stellen mithilfe von Comparator.reverseOrder() einen benutzerdefinierten Comparator bereit , um die Elemente in absteigender Reihenfolge zu sortieren. Das resultierende TreeSet enthält Elemente [7, 5, 3, 1] . Es gibt mehrere Möglichkeiten, über TreeSet zu iterieren . Wir können einen Iterator oder die erweiterte for-each- Schleife verwenden . Sehen wir uns Beispiele für beide Ansätze an:

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

Im obigen Code erstellen wir ein TreeSet namens „names“ und fügen einige Elemente hinzu. Anschließend demonstrieren wir zwei Möglichkeiten der Iteration über TreeSet : die Verwendung eines Iterators und die Verwendung der erweiterten for-each-Schleife. TreeSet bietet Methoden zur Durchführung bereichsbasierter Suchen, die es uns ermöglichen, Teilmengen von Elementen basierend auf bestimmten Kriterien abzurufen. Die drei Hauptmethoden für bereichsbasierte Suchen sind:

• subSet(E fromElement, E toElement) : Gibt eine Teilmenge der Elemente von fromElement (inklusive) bis toElement (exklusiv) zurück.
• headSet(E toElement) : Gibt eine Teilmenge von Elementen zurück, die kleiner als toElement sind .
• tailSet(E fromElement) : Gibt eine Teilmenge von Elementen zurück, die größer oder gleich fromElement ist .

Sehen wir uns ein Beispiel an:

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

Im obigen Code erstellen wir ein TreeSet namens „Numbers“ und fügen einige Elemente hinzu. Anschließend demonstrieren wir bereichsbasierte Suchen mit den Methoden subSet() , headSet() und tailSet() .

• Die Teilmenge TreeSet enthält Elemente zwischen 3 (einschließlich) und 8 (ausschließlich), also [3, 5, 7] .
• Das headSet TreeSet enthält Elemente mit weniger als 6, nämlich [1, 3, 5] .
• Das tailSet TreeSet enthält Elemente größer oder gleich 5, also [5, 7, 9] .

Diese bereichsbasierten Suchmethoden ermöglichen es uns, Teilmengen von Elementen basierend auf bestimmten Kriterien abzurufen und bieten so Flexibilität bei der Arbeit mit sortierten Daten.

Komparator in TreeSet: Sortieren mit benutzerdefinierten Kriterien

Abgesehen von der natürlichen Sortierung können Sie zum Sortieren von TreeSet einen benutzerdefinierten Comparator verwenden . In diesem Abschnitt werden wir uns mit dem Konzept eines Komparators und seiner Rolle in TreeSet befassen . Wir werden untersuchen, wie man ein TreeSet mit einem benutzerdefinierten Komparator erstellt, und Codebeispiele bereitstellen, um die Sortierung von TreeSet basierend auf bestimmten Kriterien zu demonstrieren.

Was ist ein Komparator?

Ein Comparator ist eine Schnittstelle in Java, die eine benutzerdefinierte Sortierung von Objekten ermöglicht. Es bietet eine Möglichkeit, die Reihenfolge von Elementen basierend auf bestimmten Attributen oder Eigenschaften zu definieren. Durch die Implementierung der Comparator- Schnittstelle und das Überschreiben ihrer Compare()- Methode können wir angeben, wie Elemente in einem TreeSet sortiert werden sollen .

TreeSet mit einem benutzerdefinierten Komparator erstellen

Um ein TreeSet mit einem benutzerdefinierten Komparator zu erstellen, müssen wir den Komparator beim Erstellen der TreeSet- Instanz als Argument angeben. Sehen wir uns ein Beispiel an:

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

Im obigen Code erstellen wir ein TreeSet namens „names“ mit einem benutzerdefinierten Komparator namens „LengthComparator “ . Der LengthComparator vergleicht die Länge zweier Strings und sortiert sie entsprechend. Als Ergebnis wird das TreeSet nach der Länge der Strings sortiert, was uns die Ausgabe [Ivy, Rick, David, Johnny] liefert .

Beispiele für das Sortieren von TreeSet mithilfe eines Komparators

Neben der Erstellung eines TreeSet mit einem benutzerdefinierten Komparator können wir einen Komparator auch verwenden, um ein TreeSet vorübergehend zu sortieren, ohne seine natürliche Reihenfolge zu ändern. Sehen wir uns ein Beispiel an:

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

Im obigen Code erstellen wir ein TreeSet namens „names“ und fügen einige Elemente hinzu. Anschließend erstellen wir ein neues TreeSet namens sortedNames mit einem benutzerdefinierten Komparator Comparator.reverseOrder() . Indem wir alle Elemente aus dem ursprünglichen Namens -TreeSet zu sortedNames hinzufügen , erhalten wir eine temporäre sortierte Version des TreeSet .

Vergleich von TreeSet mit anderen Datenstrukturen

Vergleich von TreeSet mit HashSet

Sowohl TreeSet als auch HashSet sind Implementierungen der Set- Schnittstelle in Java. Es gibt jedoch erhebliche Unterschiede zwischen ihnen. TreeSet : TreeSet speichert eindeutige Elemente in sortierter Reihenfolge. Es verwendet einen selbstausgleichenden binären Suchbaum (normalerweise ein Rot-Schwarz-Baum), um die sortierte Reihenfolge beizubehalten, was zu einer logarithmischen Zeitkomplexität für Vorgänge wie Einfügen, Löschen und Suchen führt. TreeSet ist effizient für die Pflege einer sortierten Sammlung und die Durchführung bereichsbasierter Vorgänge. Allerdings hat es aufgrund der Baumstruktur einen höheren Speicheraufwand und lässt keine Nullelemente zu. HashSet : HashSet speichert eindeutige Elemente in ungeordneter Weise mithilfe von Hash-Codes und einer internen Hashtabelle. Es bietet eine konstante Zeitkomplexität für grundlegende Vorgänge wie Einfügen, Löschen und Suchen. HashSet ist effizient für die schnelle Elementsuche und verursacht keinen zusätzlichen Speicheraufwand für die Aufrechterhaltung der Reihenfolge. Es garantiert jedoch keine bestimmte Reihenfolge der Elemente.

Wann man TreeSet verwendet:

• Wenn Sie Elemente automatisch in einer sortierten Reihenfolge verwalten müssen.
• Wenn Sie bereichsbasierte Operationen benötigen oder Elemente innerhalb eines bestimmten Bereichs effizient finden müssen.
• Wenn doppelte Elemente nicht zulässig sind und Eindeutigkeit unerlässlich ist.
• Wenn Sie bereit sind, einen etwas höheren Speicherverbrauch gegen die Vorteile automatischer Sortier- und Bereichsvorgänge in Kauf zu nehmen.

Vergleich von TreeSet mit ArrayList

ArrayList ist eine dynamische Array-Implementierung in Java. Hier sind die Hauptunterschiede zwischen TreeSet und ArrayList :

• TreeSet : TreeSet speichert eindeutige Elemente in sortierter Reihenfolge und bietet so effiziente Vorgänge zum Verwalten einer sortierten Sammlung und zum Durchführen bereichsbasierter Suchen. Es weist eine logarithmische Zeitkomplexität für Operationen auf. TreeSet ist nicht für den Direktzugriff oder die Beibehaltung der Einfügereihenfolge geeignet.
• ArrayList : ArrayList speichert Elemente in der Reihenfolge ihrer Einfügung und ermöglicht so einen schnellen Direktzugriff auf Elemente mithilfe von Indizes. Beim Zugriff auf Elemente über den Index weist es für die meisten Vorgänge eine konstante Zeitkomplexität auf. Das Einfügen oder Entfernen von Elementen aus der Mitte der Liste erfordert jedoch eine lineare Zeitkomplexität, da Elemente verschoben werden müssen.

Wann sollten andere Datenstrukturen in Betracht gezogen werden?

• Wenn die Pflege von Elementen in sortierter Reihenfolge nicht erforderlich ist und Sie eine schnelle Elementsuche oder eine ungeordnete Sammlung benötigen, ist HashSet möglicherweise die bessere Wahl.
• Wenn Sie häufigen Direktzugriff auf Elemente nach Index benötigen oder die Einfügereihenfolge beibehalten müssen, ist ArrayList besser geeignet.