TreeSet di Jawa

Java menyediakan sekumpulan besar struktur data untuk bekerja secara efisien dengan kumpulan elemen. Salah satu struktur data tersebut adalah TreeSet, sebuah implementasi pohon merah-hitam di Java. TreeSet mempertahankan urutan yang diurutkan untuk menyimpan elemen unik. Pemula mungkin merasa penggunaan kelas Java TreeSet agak menantang pada awalnya. Pada artikel ini, kita akan mengetahui cara menggunakan TreeSet , menjelaskan konsep intinya dan memberikan contoh kode untuk membantu Anda mulai menggabungkan TreeSet dalam proyek Java Anda.

Struktur TreeSet: Pohon Merah-Hitam

Seperti yang kami sebutkan sebelumnya, struktur kelas Java TreeSet diimplementasikan sebagai pohon pencarian biner yang menyeimbangkan diri yang dikenal sebagai pohon Merah-Hitam. Mari kita jelaskan apa ini... Pohon Merah-Hitam mewakili struktur data pencarian biner seimbang yang biasa digunakan untuk menyimpan dan mengatur data yang diurutkan. Namanya diambil dari properti yang menjaga keseimbangannya:

Setiap simpul di pohon berwarna merah atau hitam.
Akar pohon Merah Hitam selalu berwarna hitam.
Semua node daun (node NIL atau tautan nol) berwarna hitam.
Jika simpul pohon berwarna merah, maka anak-anaknya berwarna hitam.
Setiap jalur sederhana dari sebuah node ke node turunannya berisi node hitam dalam jumlah yang sama.

Pohon merah-hitam menunjukkan kinerja yang efisien untuk operasi penyisipan, penghapusan, dan pencarian elemen dengan memastikan keseimbangan. Hal ini menjamin bahwa tinggi pohon tetap proporsional dengan logaritma jumlah node yang dikandungnya, sehingga menghasilkan kompleksitas waktu logaritmik untuk operasi. Pohon merah-hitam menemukan penerapan yang luas di berbagai domain, termasuk penerapan pohon pencarian seimbang dalam bahasa pemrograman, database (misalnya, struktur indeks internal), dan skenario lain yang memerlukan penyimpanan dan pengoperasian yang efisien pada data yang diurutkan.

Fitur dan kelemahan TreeSet

TreeSet menyediakan beberapa fitur utama yang menjadikannya alat yang berharga untuk mengelola koleksi objek secara terurut. Keuntungan:

Pemeliharaan otomatis elemen dalam urutan yang diurutkan. Saat menambahkan atau menghapus elemen, struktur pohon menyesuaikan agar elemen tersebut tetap terurut. Hal ini menghilangkan kebutuhan akan penyortiran manual dan memberikan akses yang efisien dalam urutan menaik atau menurun.
Operasi pencarian, penyisipan, dan penghapusan yang efisien. Ini menggunakan struktur pohon pencarian biner, memungkinkan operasi ini dengan kompleksitas waktu O(log N) . Di sini N adalah jumlah elemen.
TreeSet menjamin keunikan elemen dengan memanfaatkan tatanan alaminya atau Comparator khusus . Ini berguna ketika bekerja dengan koleksi yang memerlukan elemen berbeda.

Keterbatasan:

Sedikit lebih lambat dari HashSet karena mempertahankan urutan yang diurutkan.
Tidak mengizinkan elemen nol, karena bergantung pada pengurutan alami atau Komparator khusus untuk perbandingan elemen.

Java TreeSet: contoh operasi utama

Sekarang mari kita mendemonstrasikan cara membuat TreeSet di Java, mendapatkan ukuran koleksi, menambahkan elemen ke dalamnya, menghapusnya, dan memeriksa apakah ada elemen di TreeSet . Contoh kode ini mendemonstrasikan operasi utama saat bekerja dengan TreeSet : membuat sebuah instance, menambahkan elemen, menghapus elemen, memeriksa keberadaan elemen, dan mendapatkan ukuran TreeSet . Membuat instance TreeSet dan menambahkan elemen:

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

Di sini kita menggunakan metode add() untuk menambahkan 4 angka di TreeSet kita . Jika kita membuat metode utama dan menjalankan program, outputnya akan terurut (2, 7, 18, 28). Menghapus elemen dari 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]

Memeriksa keberadaan elemen di 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

Mendapatkan ukuran 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

Menyortir dan Iterasi di TreeSet

TreeSet di Java menyediakan fitur canggih untuk mengurutkan dan mengulangi kumpulan elemen. Di bagian ini, kita akan mengeksplorasi berbagai teknik untuk mengurutkan elemen, melakukan iterasi pada TreeSet , dan melakukan penelusuran berbasis rentang menggunakan metode subSet() , headSet() , dan tailSet() . Secara default, TreeSet secara otomatis memelihara elemen dalam urutan yang diurutkan. Namun, kita dapat menyesuaikan perilaku pengurutan dengan menyediakan Komparator selama pembuatan TreeSet . Mari kita lihat contohnya:

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

Pada kode di atas, kita membuat TreeSet bertipe Integer dan menyediakan Comparator khusus menggunakan Comparator.reverseOrder() untuk mengurutkan elemen dalam urutan menurun. TreeSet yang dihasilkan akan berisi elemen [7, 5, 3, 1] . Ada beberapa cara untuk mengulangi TreeSet . Kita dapat menggunakan iterator atau memanfaatkan loop for-each yang ditingkatkan . Mari kita lihat contoh kedua pendekatan tersebut:

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

Dalam kode di atas, kita membuat TreeSet yang disebut nama dan menambahkan beberapa elemen. Kami kemudian mendemonstrasikan dua cara melakukan iterasi pada TreeSet : menggunakan iterator dan memanfaatkan perulangan for-each yang ditingkatkan. TreeSet menyediakan metode untuk melakukan pencarian berbasis rentang, memungkinkan kita mengambil subkumpulan elemen berdasarkan kriteria tertentu. Tiga metode utama untuk pencarian berbasis rentang adalah:

subSet(E fromElement, E toElement) : Mengembalikan subset elemen dari fromElement (inklusif) ke toElement (eksklusif).
headSet(E toElement) : Mengembalikan subset elemen yang kurang dari toElement .
tailSet(E fromElement) : Mengembalikan subset elemen yang lebih besar atau sama dengan fromElement .

Mari kita lihat contohnya:

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

Dalam kode di atas, kita membuat TreeSet yang disebut angka dan menambahkan beberapa elemen. Kami kemudian mendemonstrasikan penelusuran berbasis rentang menggunakan metode subSet() , headSet() , dan tailSet() .

Subset TreeSet berisi elemen antara 3 (inklusif) dan 8 (eksklusif), yaitu [3, 5 , 7] .
headSet TreeSet berisi elemen kurang dari 6, yaitu [1, 3, 5 ] .
tailSet TreeSet berisi elemen yang lebih besar dari atau sama dengan 5, yaitu [5, 7, 9 ] .

Metode pencarian berbasis rentang ini memungkinkan kami mengambil subkumpulan elemen berdasarkan kriteria tertentu, memberikan fleksibilitas dalam bekerja dengan data yang diurutkan.

Pembanding di TreeSet: Menyortir dengan Kriteria Khusus

Kecuali untuk pengurutan alami, Anda dapat menggunakan Komparator khusus untuk mengurutkan TreeSet . Di bagian ini, kita akan mempelajari konsep komparator dan perannya dalam TreeSet . Kita akan mempelajari cara membuat TreeSet dengan pembanding khusus dan memberikan contoh kode untuk mendemonstrasikan pengurutan TreeSet berdasarkan kriteria tertentu.

Apa itu Komparator?

Komparator adalah antarmuka di Java yang memungkinkan pengurutan objek secara khusus . Ini menyediakan cara untuk menentukan urutan elemen berdasarkan atribut atau properti tertentu. Dengan mengimplementasikan antarmuka Comparator dan mengganti metode bandingkan() nya , kita dapat menentukan bagaimana elemen harus diurutkan dalam TreeSet .

Membuat TreeSet dengan Pembanding Kustom

Untuk membuat TreeSet dengan pembanding khusus, kita perlu menyediakan pembanding sebagai argumen saat membuat instance TreeSet . Mari kita lihat contohnya:

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

Dalam kode di atas, kita membuat TreeSet yang disebut nama dengan pembanding khusus yang disebut PanjangKomparator . LongComparator membandingkan panjang dua string dan mengurutkannya sesuai dengan itu. Hasilnya, TreeSet diurutkan berdasarkan panjang string, sehingga menghasilkan keluaran [Ivy, Rick, David, Johnny] .

Contoh Pengurutan TreeSet menggunakan Komparator

Selain membuat TreeSet dengan pembanding khusus, kita juga dapat menggunakan pembanding untuk mengurutkan TreeSet sementara tanpa mengubah urutan alaminya. Mari kita lihat contohnya:

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

Dalam kode di atas, kita membuat TreeSet yang disebut nama dan menambahkan beberapa elemen. Kami kemudian membuat TreeSet baru yang disebut sortNames dengan pembanding khusus Comparator.reverseOrder() . Dengan menambahkan semua elemen dari nama asli TreeSet ke sortNames , kita mendapatkan versi TreeSet yang diurutkan sementara .

Membandingkan TreeSet dengan Struktur Data Lainnya

Membandingkan TreeSet dengan HashSet

TreeSet dan HashSet merupakan implementasi antarmuka Set di Java. Namun, terdapat perbedaan signifikan di antara keduanya. TreeSet : TreeSet menyimpan elemen unik dalam urutan yang diurutkan. Ia menggunakan pohon pencarian biner yang menyeimbangkan dirinya sendiri (biasanya Pohon Merah-Hitam) untuk mempertahankan urutan yang diurutkan, menghasilkan kompleksitas waktu logaritmik untuk operasi seperti penyisipan, penghapusan, dan pencarian. TreeSet efisien untuk memelihara koleksi yang diurutkan dan melakukan operasi berbasis rentang. Namun, ia memiliki overhead memori yang lebih tinggi karena struktur pohon dan tidak mengizinkan elemen nol. HashSet : HashSet menyimpan elemen unik secara tidak berurutan menggunakan kode hash dan tabel hash secara internal. Ini memberikan kompleksitas waktu yang konstan untuk operasi dasar seperti penyisipan, penghapusan, dan pencarian. HashSet efisien untuk pencarian elemen cepat dan tidak membebankan overhead memori tambahan untuk menjaga ketertiban. Namun, ini tidak menjamin urutan elemen tertentu.

Kapan Menggunakan TreeSet:

Saat Anda perlu mempertahankan elemen dalam urutan yang terurut secara otomatis.
Saat Anda memerlukan operasi berbasis rentang atau perlu menemukan elemen dalam rentang tertentu secara efisien.
Ketika elemen duplikat tidak diperbolehkan dan keunikan sangat penting.
Ketika Anda bersedia mengorbankan penggunaan memori yang sedikit lebih tinggi demi keuntungan operasi penyortiran dan jangkauan otomatis.

Membandingkan TreeSet dengan ArrayList

ArrayList adalah implementasi array dinamis di Java. Berikut adalah perbedaan utama antara TreeSet dan ArrayList :

TreeSet : TreeSet menyimpan elemen unik dalam urutan yang diurutkan, menyediakan operasi yang efisien untuk memelihara koleksi yang diurutkan dan melakukan pencarian berbasis rentang. Ini memiliki kompleksitas waktu logaritmik untuk operasi. TreeSet tidak cocok untuk akses acak atau mempertahankan urutan penyisipan.
ArrayList : ArrayList menyimpan elemen dalam urutan penyisipan, menyediakan akses acak cepat ke elemen menggunakan indeks. Ini memiliki kompleksitas waktu yang konstan untuk sebagian besar operasi saat mengakses elemen berdasarkan indeks. Namun, ia memiliki kompleksitas waktu linier untuk menyisipkan atau menghapus elemen dari tengah daftar, karena memerlukan perpindahan elemen.

Kapan Mempertimbangkan Struktur Data Lainnya

Jika mempertahankan elemen dalam urutan terurut tidak diperlukan, dan Anda memerlukan pencarian elemen cepat atau koleksi tidak berurutan, HashSet mungkin merupakan pilihan yang lebih baik.
Jika Anda sering memerlukan akses acak ke elemen berdasarkan indeks atau perlu menjaga urutan penyisipan, ArrayList akan lebih cocok.