TreeSet sa Java

Nagbibigay ang Java ng malawak na hanay ng mga istruktura ng data para sa mahusay na pagtatrabaho sa mga koleksyon ng elemento. Ang isa sa gayong istruktura ng data ay ang TreeSet, isang pagpapatupad ng isang pulang-itim na puno sa Java. Ang TreeSet ay nagpapanatili ng isang pinagsunod-sunod na pagkakasunud-sunod para sa pag-iimbak ng mga natatanging elemento. Maaaring makita ng mga nagsisimula ang paggamit ng Java TreeSet class na medyo mahirap sa simula. Sa artikulong ito, aalamin namin kung paano gamitin ang TreeSet , na nagpapaliwanag sa mga pangunahing konsepto nito at nagbibigay ng mga halimbawa ng code upang matulungan kang simulan ang pagsasama ng TreeSet sa iyong mga proyekto sa Java.

Istraktura ng TreeSet: Pula-Itim na puno

Gaya ng nabanggit namin dati, ang istraktura ng klase ng Java TreeSet ay ipinatupad bilang isang self-balancing binary search tree na kilala bilang isang Red-Black tree. Ipaliwanag natin kung ano ito... Ang Red-Black Tree ay kumakatawan sa isang balanseng binary search data structure na karaniwang ginagamit upang mag-imbak at mag-ayos ng pinagsunod-sunod na data. Kinukuha nito ang pangalan nito mula sa mga katangian na nagpapanatili ng balanse nito:

• Ang bawat node sa puno ay pula o itim.
• Ang ugat ng Pula-Itim na puno ay laging itim.
• Ang lahat ng leaf node (NIL node o null links) ay itim.
• Kung ang isang node ng puno ay pula, ang mga anak nito ay itim.
• Ang bawat simpleng landas mula sa isang node hanggang sa mga descendant node nito ay naglalaman ng pantay na bilang ng mga itim na node.

Ang mga pulang-itim na puno ay nagpapakita ng mahusay na pagganap para sa mga operasyon ng pagpasok, pagtanggal, at paghahanap ng elemento sa pamamagitan ng pagtiyak ng balanse. Tinitiyak nito na ang taas ng puno ay nananatiling proporsyonal sa logarithm ng bilang ng mga node na nilalaman nito, na nagreresulta sa pagiging kumplikado ng oras ng logarithmic para sa mga operasyon. Ang mga pulang-itim na puno ay nakakahanap ng malawak na aplikasyon sa iba't ibang mga domain, kabilang ang pagpapatupad ng mga balanseng puno ng paghahanap sa mga programming language, mga database (hal., mga panloob na istruktura ng index), at iba pang mga sitwasyon kung saan kinakailangan ang mahusay na pag-iimbak at mga operasyon sa pinagsunod-sunod na data.

Mga tampok at kahinaan ng TreeSet

Nagbibigay ang TreeSet ng ilang pangunahing tampok na ginagawa itong isang mahalagang tool para sa pamamahala ng mga koleksyon ng mga bagay sa isang pinagsunod-sunod na paraan. Mga kalamangan:

• Awtomatikong pagpapanatili ng mga elemento sa pinagsunod-sunod na pagkakasunud-sunod. Kapag nagdadagdag o nag-aalis ng mga elemento, ang istraktura ng puno ay nag-a-adjust para panatilihing maayos ang mga ito. Inaalis nito ang pangangailangan para sa manu-manong pag-uuri at nagbibigay ng mahusay na pag-access sa pataas o pababang pagkakasunud-sunod.
• Mahusay na paghahanap, pagpasok, at pagtanggal ng mga operasyon. Gumagamit ito ng binary search tree structure, na nagpapagana sa mga operasyong ito na may time complexity ng O(log N) . Narito ang N ay ang bilang ng mga elemento.
• Ginagarantiyahan ng TreeSet ang pagiging natatangi ng mga elemento sa pamamagitan ng paggamit ng kanilang natural na pagkakasunud-sunod o isang custom na Comparator . Ito ay kapaki-pakinabang kapag nagtatrabaho sa mga koleksyon na nangangailangan ng mga natatanging elemento.

Mga Limitasyon:

• Bahagyang mas mabagal kaysa sa HashSet dahil sa pagpapanatili ng pinagsunod-sunod na pagkakasunud-sunod.
• Hindi pinapayagan ang mga null na elemento, dahil umaasa ito sa natural na pag-order o isang custom na Comparator para sa paghahambing ng elemento.

Java TreeSet: halimbawa ng mga pangunahing operasyon

Ngayon ipakita natin kung paano lumikha ng TreeSet sa Java, kunin ang laki ng koleksyon, magdagdag ng mga elemento dito, alisin ang mga ito at tingnan kung ang isang elemento ay nasa TreeSet . Ang mga halimbawa ng code na ito ay nagpapakita ng mga pangunahing operasyon kapag nagtatrabaho sa TreeSet : paglikha ng isang instance, pagdaragdag ng mga elemento, pag-alis ng mga elemento, pagsuri para sa presensya ng elemento, at pagkuha ng laki ng TreeSet . Paglikha ng isang halimbawa ng TreeSet at pagdaragdag ng mga elemento:

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

Dito ginagamit namin ang paraan ng add() upang magdagdag ng 4 na numero sa aming TreeSet . Kung gagawa tayo ng pangunahing paraan at patakbuhin ang programa, ang output ay nasa ayos na pagkakasunod-sunod (2, 7, 18, 28). Pag-alis ng mga elemento mula sa 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]

Sinusuri ang pagkakaroon ng isang elemento sa 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

Pagkuha ng laki ng 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

Pag-uuri at Pag-ulit sa TreeSet

Nagbibigay ang TreeSet sa Java ng mga mahuhusay na feature para sa pag-uuri at pag-ulit sa mga koleksyon ng mga elemento. Sa seksyong ito, tutuklasin natin ang iba't ibang mga diskarte para sa pag-uuri ng mga elemento, pag-ulit sa TreeSet , at pagsasagawa ng mga paghahanap na nakabatay sa hanay gamit ang subSet() , headSet() , at tailSet() na mga pamamaraan. Bilang default, awtomatikong pinapanatili ng TreeSet ang mga elemento sa pinagsunod-sunod na pagkakasunud-sunod. Gayunpaman, maaari naming i-customize ang pag-uuri ng gawi sa pamamagitan ng pagbibigay ng Comparator sa panahon ng paglikha ng TreeSet . Tingnan natin ang isang halimbawa:

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

Sa code sa itaas, gumawa kami ng TreeSet ng uri ng Integer at nagbibigay ng custom na Comparator gamit ang Comparator.reverseOrder() upang pagbukud-bukurin ang mga elemento sa pababang pagkakasunud-sunod. Ang resultang TreeSet ay maglalaman ng mga elemento [7, 5, 3, 1] . Mayroong maraming mga paraan upang umulit sa TreeSet . Maaari kaming gumamit ng isang iterator o gamitin ang pinahusay na para sa bawat loop. Tingnan natin ang mga halimbawa ng parehong diskarte:

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

Sa code sa itaas, lumikha kami ng TreeSet na tinatawag na mga pangalan at magdagdag ng ilang elemento. Pagkatapos ay ipinapakita namin ang dalawang paraan ng pag-ulit sa TreeSet : gamit ang isang iterator at paggamit ng pinahusay na para sa bawat loop. Nagbibigay ang TreeSet ng mga pamamaraan upang magsagawa ng mga paghahanap na nakabatay sa hanay, na nagbibigay-daan sa amin na kunin ang mga subset ng mga elemento batay sa partikular na pamantayan. Ang tatlong pangunahing paraan para sa mga paghahanap na nakabatay sa hanay ay:

• subSet(E fromElement, E toElement) : Nagbabalik ng subset ng mga elemento mula fromElement (inclusive) hanggang toElement (eksklusibo).
• headSet(E toElement) : Nagbabalik ng subset ng mga elementong mas mababa sa toElement .
• tailSet(E fromElement) : Nagbabalik ng subset ng mga elementong mas malaki sa o katumbas ng fromElement .

Tingnan natin ang isang halimbawa:

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

Sa code sa itaas, lumikha kami ng TreeSet na tinatawag na mga numero at magdagdag ng ilang elemento. Pagkatapos ay ipinapakita namin ang mga paghahanap na nakabatay sa hanay gamit ang subSet() , headSet() , at tailSet() na mga pamamaraan.

• Ang subset na TreeSet ay naglalaman ng mga elemento sa pagitan ng 3 (inclusive) at 8 (exclusive), na [3, 5, 7] .
• Ang headSet TreeSet ay naglalaman ng mga elementong mas mababa sa 6, na [1, 3, 5] .
• Ang tailSet TreeSet ay naglalaman ng mga elementong mas malaki sa o katumbas ng 5, na [5, 7, 9] .

Nagbibigay-daan sa amin ang mga paraan ng paghahanap na nakabatay sa hanay na ito na kumuha ng mga subset ng mga elemento batay sa partikular na pamantayan, na nagbibigay ng flexibility sa pagtatrabaho sa pinagsunod-sunod na data.

Comparator sa TreeSet: Pag-uuri gamit ang Custom na Pamantayan

Maliban sa natural na pag-order, maaari kang gumamit ng custom na Comparator para sa pag-uuri ng TreeSet . Sa seksyong ito, susuriin natin ang konsepto ng isang comparator at ang papel nito sa TreeSet . Tuklasin namin kung paano lumikha ng TreeSet na may custom na comparator at magbigay ng mga halimbawa ng code upang ipakita ang pag-uuri ng TreeSet batay sa partikular na pamantayan.

Ano ang Comparator?

Ang Comparator ay isang interface sa Java na nagbibigay-daan sa custom na pag-uuri ng mga bagay. Nagbibigay ito ng paraan upang tukuyin ang pagkakasunud-sunod ng mga elemento batay sa mga partikular na katangian o katangian. Sa pamamagitan ng pagpapatupad ng interface ng Comparator at pag-override sa paraan ng compare() nito , matutukoy natin kung paano dapat pagbukud-bukurin ang mga elemento sa isang TreeSet .

Paggawa ng TreeSet gamit ang Custom Comparator

Para gumawa ng TreeSet na may custom na comparator, kailangan naming ibigay ang comparator bilang argumento kapag gumagawa ng TreeSet instance. Tingnan natin ang isang halimbawa:

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

Sa code sa itaas, gumawa kami ng TreeSet na tinatawag na mga pangalan na may custom na comparator na tinatawag na LengthComparator . Inihahambing ng LengthComparator ang haba ng dalawang string at pinag-uuri ang mga ito nang naaayon. Bilang resulta, ang TreeSet ay pinagsunod-sunod batay sa haba ng mga string, na nagbibigay sa amin ng output [Ivy, Rick, David, Johnny] .

Mga halimbawa ng Pag-uuri ng TreeSet gamit ang isang Comparator

Bukod sa paggawa ng TreeSet na may custom na comparator, maaari rin kaming gumamit ng comparator para pansamantalang ayusin ang TreeSet nang hindi binabago ang natural na pagkakasunud-sunod nito. Tingnan natin ang isang halimbawa:

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

Sa code sa itaas, lumikha kami ng TreeSet na tinatawag na mga pangalan at magdagdag ng ilang elemento. Pagkatapos ay gumawa kami ng bagong TreeSet na tinatawag na sortedNames na may custom na comparator Comparator.reverseOrder() . Sa pamamagitan ng pagdaragdag ng lahat ng elemento mula sa orihinal na mga pangalang TreeSet sa sortedNames , nakakakuha kami ng pansamantalang pinagsunod-sunod na bersyon ng TreeSet .

Paghahambing ng TreeSet sa Iba Pang Mga Structure ng Data

Paghahambing ng TreeSet sa HashSet

Parehong TreeSet at HashSet ay mga pagpapatupad ng Set interface sa Java. Gayunpaman, may mga makabuluhang pagkakaiba sa pagitan nila. TreeSet : Nag-iimbak ang TreeSet ng mga natatanging elemento sa pinagsunod-sunod na pagkakasunud-sunod. Gumagamit ito ng self-balancing binary search tree (karaniwan ay isang Red-Black Tree) upang mapanatili ang pinagsunod-sunod na pagkakasunud-sunod, na nagreresulta sa logarithmic time complexity para sa mga operasyon tulad ng pagpasok, pagtanggal, at paghahanap. Ang TreeSet ay mahusay para sa pagpapanatili ng isang pinagsunod-sunod na koleksyon at pagsasagawa ng mga operasyong nakabatay sa saklaw. Gayunpaman, mayroon itong mas mataas na memory overhead dahil sa istraktura ng puno at hindi pinapayagan ang mga null na elemento. HashSet : Ang HashSet ay nag-iimbak ng mga natatanging elemento sa hindi ayos na paraan gamit ang mga hash code at hashtable sa loob. Nagbibigay ito ng patuloy na pagiging kumplikado ng oras para sa mga pangunahing operasyon tulad ng pagpasok, pagtanggal, at paghahanap. Ang HashSet ay mahusay para sa mabilis na paghahanap ng elemento at hindi nagpapataw ng anumang karagdagang memory overhead para sa pagpapanatili ng kaayusan. Gayunpaman, hindi nito ginagarantiyahan ang anumang partikular na pag-order ng mga elemento.

Kailan Gamitin ang TreeSet:

• Kapag kailangan mong mapanatili ang mga elemento sa isang nakaayos na pagkakasunud-sunod nang awtomatiko.
• Kapag kailangan mo ng mga operasyong nakabatay sa saklaw o kailangan mong maghanap ng mga elemento sa loob ng isang partikular na hanay nang mahusay.
• Kapag hindi pinapayagan ang mga dobleng elemento at mahalaga ang pagiging natatangi.
• Kapag handa kang ipagpalit ang bahagyang mas mataas na paggamit ng memory para sa mga benepisyo ng awtomatikong pag-uuri at pagpapatakbo ng hanay.

Paghahambing ng TreeSet sa ArrayList

Ang ArrayList ay isang dynamic na pagpapatupad ng array sa Java. Narito ang mga pangunahing pagkakaiba sa pagitan ng TreeSet at ArrayList :

• TreeSet : Nag-iimbak ang TreeSet ng mga natatanging elemento sa pinagsunod-sunod na pagkakasunud-sunod, na nagbibigay ng mahusay na mga operasyon para sa pagpapanatili ng isang pinagsunod-sunod na koleksyon at pagsasagawa ng mga paghahanap na nakabatay sa hanay. Mayroon itong logarithmic time complexity para sa mga operasyon. Ang TreeSet ay hindi angkop para sa random na pag-access o pagpapanatili ng pagkakasunud-sunod ng pagpasok.
• ArrayList : Ang ArrayList ay nag-iimbak ng mga elemento sa pagkakasunud-sunod ng pagpasok, na nagbibigay ng mabilis na random na access sa mga elemento gamit ang mga indeks. Ito ay may patuloy na pagiging kumplikado ng oras para sa karamihan ng mga operasyon kapag nag-a-access ng mga elemento sa pamamagitan ng index. Gayunpaman, mayroon itong linear time complexity para sa pagpasok o pag-alis ng mga elemento mula sa gitna ng listahan, dahil nangangailangan ito ng paglilipat ng mga elemento.

Kailan Dapat Isaalang-alang ang Iba Pang Mga Istraktura ng Data

• Kung hindi kinakailangan ang pagpapanatili ng mga elemento sa isang pinagsunod-sunod na pagkakasunud-sunod, at kailangan mo ng isang mabilis na paghahanap ng elemento o isang hindi nakaayos na koleksyon, ang HashSet ay maaaring maging isang mas mahusay na pagpipilian.
• Kung kailangan mo ng madalas na random na pag-access sa mga elemento sa pamamagitan ng index o kailangan mong panatilihin ang pagkakasunud-sunod ng pagpapasok, ang ArrayList ay magiging mas angkop.