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