TreeSet dalam Java

Java menyediakan satu set struktur data yang luas untuk bekerja dengan cekap dengan koleksi elemen. Satu struktur data sedemikian ialah TreeSet, pelaksanaan pokok merah-hitam di Jawa. TreeSet mengekalkan susunan yang disusun untuk menyimpan elemen unik. Pemula mungkin mendapati menggunakan kelas Java TreeSet agak mencabar pada mulanya. Dalam artikel ini, kami akan memikirkan cara menggunakan TreeSet , menerangkan konsep terasnya dan menyediakan contoh kod untuk membantu anda mula menggabungkan TreeSet dalam projek Java anda.

Struktur TreeSet: Pokok Merah-Hitam

Seperti yang kami nyatakan sebelum ini, struktur kelas Java TreeSet dilaksanakan sebagai pepohon carian perduaan pengimbangan diri yang dikenali sebagai pokok Merah-Hitam. Mari jelaskan apakah ini... Pokok Merah-Hitam mewakili struktur data carian binari seimbang yang biasa digunakan untuk menyimpan dan menyusun data yang diisih. Ia mendapat namanya daripada sifat-sifat yang mengekalkan keseimbangannya:

Setiap nod dalam pokok berwarna merah atau hitam.
Akar pokok Merah-Hitam sentiasa hitam.
Semua nod daun (nod NIL atau pautan null) berwarna hitam.
Jika simpul pokok berwarna merah, maka anak-anaknya berwarna hitam.
Setiap laluan mudah dari nod ke nod keturunannya mengandungi bilangan nod hitam yang sama.

Pokok merah-hitam mempamerkan prestasi yang cekap untuk operasi pemasukan, pemadaman dan carian elemen dengan memastikan keseimbangan. Ini menjamin bahawa ketinggian pokok kekal berkadar dengan logaritma bilangan nod yang terkandung di dalamnya, mengakibatkan kerumitan masa logaritma untuk operasi. Pokok merah-hitam menemui aplikasi yang luas dalam pelbagai domain, termasuk pelaksanaan pepohon carian seimbang dalam bahasa pengaturcaraan, pangkalan data (cth, struktur indeks dalaman) dan senario lain yang memerlukan penyimpanan dan operasi yang cekap pada data yang diisih.

Ciri dan kelemahan TreeSet

TreeSet menyediakan beberapa ciri utama yang menjadikannya alat yang berharga untuk mengurus koleksi objek dalam cara yang disusun. Kelebihan:

Penyelenggaraan automatik elemen dalam susunan yang disusun. Apabila menambah atau mengalih keluar elemen, struktur pokok menyesuaikan untuk memastikan ia diisih. Ini menghapuskan keperluan untuk pengisihan manual dan menyediakan akses yang cekap dalam susunan menaik atau menurun.
Operasi carian, sisip dan padam yang cekap. Ia menggunakan struktur pokok carian binari, membolehkan operasi ini dengan kerumitan masa O(log N) . Di sini N ialah bilangan unsur.
TreeSet menjamin keunikan unsur dengan menggunakan susunan semula jadinya atau Pembanding tersuai . Ini berguna apabila bekerja dengan koleksi yang memerlukan elemen yang berbeza.

Had:

Lebih perlahan sedikit daripada HashSet kerana mengekalkan susunan yang diisih.
Tidak membenarkan unsur nol, kerana ia bergantung pada susunan semula jadi atau Pembanding tersuai untuk perbandingan unsur.

Java TreeSet: contoh operasi utama

Sekarang mari kita tunjukkan cara membuat TreeSet di Java, dapatkan saiz koleksi, tambah elemen ke dalamnya, alih keluarnya dan semak sama ada elemen berada dalam TreeSet . Contoh kod ini menunjukkan operasi utama apabila bekerja dengan TreeSet : mencipta contoh, menambah elemen, mengalih keluar elemen, menyemak kehadiran elemen dan mendapatkan saiz TreeSet . Mencipta contoh TreeSet dan menambah 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 kami menggunakan kaedah add() untuk menambah 4 nombor dalam TreeSet kami . Jika kita mencipta kaedah utama dan menjalankan program, output akan disusun mengikut urutan (2, 7, 18, 28). Mengalih keluar elemen daripada 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]

Menyemak kehadiran elemen dalam 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 saiz 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

Isih dan Lelaran dalam TreeSet

TreeSet dalam Java menyediakan ciri yang berkuasa untuk menyusun dan mengulang koleksi elemen. Dalam bahagian ini, kami akan meneroka pelbagai teknik untuk mengisih elemen, mengulangi TreeSet , dan melaksanakan carian berasaskan julat menggunakan kaedah subSet() , headSet() dan tailSet() . Secara lalai, TreeSet secara automatik mengekalkan elemen dalam susunan yang disusun. Walau bagaimanapun, kami boleh menyesuaikan tingkah laku pengisihan dengan menyediakan Comparator semasa penciptaan TreeSet . Mari lihat contoh:


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

Dalam kod di atas, kami mencipta TreeSet jenis Integer dan menyediakan Comparator tersuai menggunakan Comparator.reverseOrder() untuk mengisih elemen dalam tertib menurun. TreeSet yang dihasilkan akan mengandungi elemen [7, 5, 3, 1] . Terdapat pelbagai cara untuk mengulangi TreeSet . Kita boleh menggunakan iterator atau menggunakan gelung yang dipertingkatkan untuk setiap . Mari lihat contoh kedua-dua pendekatan:


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 kod di atas, kami mencipta TreeSet yang dipanggil nama dan menambah beberapa elemen. Kami kemudian menunjukkan dua cara lelaran ke atas TreeSet : menggunakan iterator dan menggunakan gelung yang dipertingkatkan untuk setiap. TreeSet menyediakan kaedah untuk melakukan carian berasaskan julat, membolehkan kami mendapatkan subset elemen berdasarkan kriteria tertentu. Tiga kaedah utama untuk carian berasaskan julat ialah:

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

Mari lihat contoh:


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 kod di atas, kami mencipta TreeSet dipanggil nombor dan menambah beberapa elemen. Kami kemudian menunjukkan carian berasaskan julat menggunakan kaedah subSet() , headSet() dan tailSet() .

Subset TreeSet mengandungi elemen antara 3 (inklusif) dan 8 (eksklusif) , iaitu [3, 5, 7] .
HeadSet TreeSet mengandungi elemen kurang daripada 6, iaitu [1 , 3, 5] .
tailSet TreeSet mengandungi elemen yang lebih besar daripada atau sama dengan 5, iaitu [5, 7, 9] .

Kaedah carian berasaskan julat ini membolehkan kami mendapatkan semula subset elemen berdasarkan kriteria tertentu, memberikan fleksibiliti dalam bekerja dengan data yang diisih.

Pembanding dalam TreeSet: Isih dengan Kriteria Tersuai

Kecuali untuk pesanan semula jadi, anda boleh menggunakan Comparator tersuai untuk mengisih TreeSet . Dalam bahagian ini, kita akan menyelidiki konsep pembanding dan peranannya dalam TreeSet . Kami akan meneroka cara mencipta TreeSet dengan pembanding tersuai dan menyediakan contoh kod untuk menunjukkan pengisihan TreeSet berdasarkan kriteria tertentu.

Apa itu Comparator?

Comparator ialah antara muka dalam Java yang membenarkan pengisihan objek tersuai. Ia menyediakan cara untuk menentukan susunan elemen berdasarkan atribut atau sifat tertentu. Dengan melaksanakan antara muka Comparator dan mengatasi kaedah compare() nya , kita boleh menentukan cara elemen harus diisih dalam TreeSet .

Mencipta TreeSet dengan Pembanding Tersuai

Untuk mencipta TreeSet dengan pembanding tersuai, kita perlu menyediakan pembanding sebagai hujah apabila mencipta contoh TreeSet . Mari lihat contoh:


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 kod di atas, kami mencipta TreeSet yang dipanggil nama dengan pembanding tersuai yang dipanggil LengthComparator . LengthComparator membandingkan panjang dua rentetan dan menyusunnya dengan sewajarnya. Hasilnya, TreeSet diisih berdasarkan panjang rentetan, memberikan kita output [Ivy, Rick, David, Johnny] .

Contoh Menyusun TreeSet menggunakan Comparator

Selain mencipta TreeSet dengan pembanding tersuai, kami juga boleh menggunakan pembanding untuk mengisih TreeSet buat sementara waktu tanpa mengubah susunan semula jadinya. Mari lihat contoh:


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 kod di atas, kami mencipta TreeSet yang dipanggil nama dan menambah beberapa elemen. Kami kemudian mencipta TreeSet baharu yang dipanggil sortedNames dengan pembanding tersuai Comparator.reverseOrder() . Dengan menambahkan semua elemen daripada nama asal TreeSet kepada sortedNames , kami memperoleh versi disusun sementara bagi TreeSet .

Membandingkan TreeSet dengan Struktur Data Lain

Membandingkan TreeSet dengan HashSet

Kedua-dua TreeSet dan HashSet ialah pelaksanaan antara muka Set dalam Java. Walau bagaimanapun, terdapat perbezaan yang ketara antara mereka. TreeSet : TreeSet menyimpan elemen unik dalam susunan yang disusun. Ia menggunakan pepohon carian perduaan pengimbangan diri (biasanya Pokok Merah-Hitam) untuk mengekalkan susunan yang diisih, menghasilkan kerumitan masa logaritma untuk operasi seperti sisipan, pemadaman dan carian. TreeSet cekap untuk mengekalkan koleksi yang diisih dan melaksanakan operasi berasaskan julat. Walau bagaimanapun, ia mempunyai overhed memori yang lebih tinggi disebabkan oleh struktur pokok dan tidak membenarkan unsur nol. HashSet : HashSet menyimpan elemen unik dalam cara yang tidak teratur menggunakan kod cincang dan jadual cincang secara dalaman. Ia menyediakan kerumitan masa yang berterusan untuk operasi asas seperti sisipan, pemadaman dan carian. HashSet adalah cekap untuk carian elemen pantas dan tidak mengenakan sebarang overhed memori tambahan untuk mengekalkan ketertiban. Walau bagaimanapun, ia tidak menjamin sebarang susunan elemen tertentu.

Bila hendak menggunakan TreeSet:

Apabila anda perlu mengekalkan elemen dalam susunan yang diisih secara automatik.
Apabila anda memerlukan operasi berasaskan julat atau perlu mencari elemen dalam julat tertentu dengan cekap.
Apabila elemen pendua tidak dibenarkan dan keunikan adalah penting.
Apabila anda sanggup menukar penggunaan memori yang lebih tinggi sedikit untuk faedah operasi pengisihan dan julat automatik.

Membandingkan TreeSet dengan ArrayList

ArrayList ialah pelaksanaan tatasusunan dinamik dalam Java. Berikut ialah perbezaan utama antara TreeSet dan ArrayList :

TreeSet : TreeSet menyimpan elemen unik dalam susunan yang disusun, menyediakan operasi yang cekap untuk mengekalkan koleksi yang diisih dan melaksanakan carian berasaskan julat. Ia mempunyai kerumitan masa logaritma untuk operasi. TreeSet tidak sesuai untuk akses rawak atau mengekalkan susunan pemasukan.
ArrayList : ArrayList menyimpan elemen dalam susunan sisipan, menyediakan akses rawak pantas kepada elemen menggunakan indeks. Ia mempunyai kerumitan masa yang berterusan untuk kebanyakan operasi apabila mengakses elemen mengikut indeks. Walau bagaimanapun, ia mempunyai kerumitan masa linear untuk memasukkan atau mengalih keluar elemen dari tengah senarai, kerana ia memerlukan elemen peralihan.

Bila Perlu Pertimbangkan Struktur Data Lain

Jika mengekalkan elemen dalam susunan yang diisih tidak diperlukan dan anda memerlukan carian elemen yang pantas atau koleksi tidak tertib, HashSet mungkin merupakan pilihan yang lebih baik.
Jika anda memerlukan akses rawak yang kerap kepada elemen mengikut indeks atau perlu mengekalkan susunan sisipan, ArrayList akan lebih sesuai.