Java มีชุดโครงสร้างข้อมูลมากมายสำหรับการทำงานกับคอลเลกชันองค์ประกอบอย่างมีประสิทธิภาพ โครงสร้างข้อมูลอย่างหนึ่งคือ TreeSet ซึ่งเป็นการนำต้นไม้สีแดงดำไปใช้ใน Java TreeSetรักษาลำดับการจัดเรียงสำหรับการจัดเก็บองค์ประกอบที่ไม่ซ้ำใคร ผู้เริ่มต้นอาจพบว่าการใช้คลาส Java TreeSetค่อนข้างท้าทายในตอนแรก ในบทความนี้ เราจะมาดูวิธีใช้TreeSetโดยอธิบายแนวคิดหลักของ TreeSet และให้ตัวอย่างโค้ดเพื่อช่วยให้คุณเริ่มรวมTreeSet เข้า กับโปรเจ็กต์ Java ของคุณ
โครงสร้าง TreeSet: ต้นไม้สีแดง-ดำ
ดังที่เราได้กล่าวไว้ก่อนหน้านี้ โครงสร้างคลาส Java TreeSetถูกนำมาใช้เป็นแผนผังการค้นหาแบบไบนารีที่ปรับสมดุลในตัวเองซึ่งเรียกว่าแผนผังสีแดง-ดำ เรามาอธิบายว่าสิ่งนี้คืออะไร... ต้นไม้สีแดง-ดำ แสดงถึงโครงสร้างข้อมูลการค้นหาแบบไบนารีที่สมดุล ซึ่งมักใช้ในการจัดเก็บและจัดระเบียบข้อมูลที่เรียงลำดับ ได้ชื่อมาจากคุณสมบัติที่ช่วยรักษาสมดุล:- แต่ละโหนดในแผนผังเป็นสีแดงหรือสีดำ
- รากของต้นแดงดำจะมีสีดำอยู่เสมอ
- โหนดลีฟทั้งหมด (โหนด NIL หรือลิงก์ว่าง) จะเป็นสีดำ
- หากโหนดของต้นไม้เป็นสีแดง ลูกของมันก็จะเป็นสีดำ
- เส้นทางง่ายๆ ทุกเส้นทางจากโหนดไปยังโหนดที่สืบทอดนั้นมีจำนวนโหนดสีดำเท่ากัน
คุณสมบัติและจุดอ่อนของ TreeSet
TreeSetมีคุณสมบัติหลักหลายประการที่ทำให้เป็นเครื่องมืออันทรงคุณค่าสำหรับการจัดการคอลเลกชันของออบเจ็กต์ในลักษณะที่เรียงลำดับ ข้อดี:- การบำรุงรักษาองค์ประกอบตามลำดับการจัดเรียงโดยอัตโนมัติ เมื่อเพิ่มหรือลบองค์ประกอบ โครงสร้างแบบต้นไม้จะปรับเพื่อให้เรียงลำดับ ซึ่งช่วยลดความจำเป็นในการเรียงลำดับด้วยตนเองและให้การเข้าถึงที่มีประสิทธิภาพจากน้อยไปหามากหรือจากมากไปน้อย
- การค้นหา แทรก และลบการดำเนินการที่มีประสิทธิภาพ ใช้โครงสร้างแผนผังการค้นหาแบบไบนารี ซึ่งช่วยให้ดำเนินการเหล่า นี้ด้วยความซับซ้อนของเวลาO(log N) โดยที่Nคือจำนวนองค์ประกอบ
- TreeSetรับประกันความเป็นเอกลักษณ์ขององค์ประกอบโดยใช้การเรียงลำดับตามธรรมชาติหรือตัวเปรียบเทียบ แบบกำหนดเอง สิ่งนี้มีประโยชน์เมื่อทำงานกับคอลเลกชันที่ต้องใช้องค์ประกอบที่แตกต่างกัน
- ช้ากว่าHashSet เล็กน้อย เนื่องจากการรักษาลำดับการเรียงลำดับ
- ไม่อนุญาตให้มีองค์ประกอบที่เป็นโมฆะ เนื่องจากต้องอาศัยการเรียงลำดับตามธรรมชาติหรือตัวเปรียบเทียบ ที่กำหนดเอง สำหรับการเปรียบเทียบองค์ประกอบ
Java TreeSet: ตัวอย่างของการดำเนินการหลัก
ตอนนี้เรามาสาธิตวิธีการสร้างTreeSetใน Java, รับขนาดของคอลเลกชัน, เพิ่มองค์ประกอบเข้าไป, ลบออกจากและตรวจสอบว่าองค์ประกอบอยู่ใน TreeSet หรือไม่ ตัวอย่างโค้ดเหล่านี้สาธิตการทำงานหลักเมื่อทำงานกับTreeSet ได้แก่การสร้างอินสแตนซ์ การเพิ่มองค์ประกอบ การลบองค์ประกอบ การตรวจสอบการมีอยู่ขององค์ประกอบ และการรับขนาดของTreeSet การสร้าง อินสแตนซ์ TreeSetและเพิ่มองค์ประกอบ:// 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]
ที่นี่เราใช้ เมธอด add()เพื่อเพิ่มตัวเลข 4 ตัวในTreeSet ของ เรา หากเราสร้าง เมธอด หลักและรันโปรแกรม ผลลัพธ์จะเรียงลำดับ (2, 7, 18, 28) การลบองค์ประกอบออกจาก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]
การตรวจสอบการมีอยู่ขององค์ประกอบใน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
รับขนาดของ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
การเรียงลำดับและการวนซ้ำใน TreeSet
TreeSetใน Java มีคุณสมบัติอันทรงพลังสำหรับการเรียงลำดับและการวนซ้ำคอลเลกชันขององค์ประกอบ ในส่วนนี้ เราจะสำรวจเทคนิคต่างๆ สำหรับการเรียงลำดับองค์ประกอบ การวนซ้ำTreeSetและการดำเนินการค้นหาตามช่วงโดยใช้เมธอดsubSet () , headSet()และtailSet() ตามค่าเริ่มต้นTreeSetจะรักษาองค์ประกอบตามลำดับการจัดเรียงโดยอัตโนมัติ อย่างไรก็ตาม เราสามารถปรับแต่งพฤติกรรมการเรียงลำดับได้โดยจัดให้มีตัวเปรียบเทียบระหว่างการสร้างTreeSet ลองดูตัวอย่าง: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]
}
}
ในโค้ดด้านบน เราสร้างTreeSetประเภท Integer และจัดเตรียมComparator แบบกำหนดเอง โดยใช้Comparator.reverseOrder()เพื่อเรียงลำดับองค์ประกอบจากมากไปน้อย TreeSetที่ได้จะมีองค์ประกอบ[7, 5, 3, 1 ] มีหลายวิธีในการวนซ้ำบนTreeSet เราสามารถใช้ตัววนซ้ำหรือใช้for-each loop ที่ปรับปรุงแล้ว ลองดูตัวอย่างของทั้งสองวิธี:
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);
}
}
}
ในโค้ดข้างต้น เราสร้างTreeSetที่เรียกว่าชื่อและเพิ่มองค์ประกอบบางอย่าง จากนั้นเราจะสาธิตการวนซ้ำTreeSet สองวิธี : การใช้ตัววนซ้ำ และการใช้ for-each loop ที่ปรับปรุงแล้ว TreeSet จัดเตรียมวิธีการในการค้นหาตามช่วง ซึ่งช่วยให้เราสามารถดึงข้อมูลชุดย่อยขององค์ประกอบตามเกณฑ์เฉพาะได้ วิธีการหลักสามวิธีสำหรับการค้นหาตามช่วงคือ:
- subSet(E fromElement, E toElement) : ส่งคืนเซตย่อยขององค์ประกอบจากfromElement (รวม) ถึงtoElement (ไม่รวม)
- headSet(E toElement) : ส่งกลับเซ็ตย่อยขององค์ประกอบที่น้อยกว่าtoElement
- tailSet(E fromElement) : ส่งกลับเซ็ต ย่อยขององค์ประกอบที่มากกว่าหรือเท่ากับ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]
}
}
ในโค้ดข้างต้น เราสร้างTreeSetที่เรียกว่า number และเพิ่มองค์ประกอบบางส่วน จากนั้นเราจะสาธิตการค้นหาตามช่วงโดยใช้เมธอดsubSet() , headSet()และtailSet()
- เซ็ตย่อย TreeSet มีองค์ประกอบระหว่าง 3 (รวม) และ8 (ไม่รวม) ซึ่งก็คือ[3, 5, 7]
- headSet TreeSetมีองค์ประกอบที่น้อยกว่า 6 ซึ่งได้แก่ [1 , 3 , 5]
- tailSet TreeSetมีองค์ประกอบที่มากกว่าหรือเท่ากับ 5 ซึ่งก็คือ[ 5, 7, 9 ]
ตัวเปรียบเทียบใน TreeSet: การเรียงลำดับด้วยเกณฑ์ที่กำหนดเอง
ยกเว้นการเรียงลำดับตามธรรมชาติ คุณสามารถใช้Comparator แบบกำหนด เองสำหรับการเรียงลำดับTreeSet ในส่วนนี้ เราจะเจาะลึกแนวคิดของตัวเปรียบเทียบและบทบาทของมันในTreeSet เราจะสำรวจวิธีการสร้างTreeSetด้วยตัวเปรียบเทียบที่กำหนดเอง และจัดเตรียมตัวอย่างโค้ดเพื่อสาธิตการเรียงลำดับ TreeSetตามเกณฑ์เฉพาะเครื่องมือเปรียบเทียบคืออะไร?
Comparator เป็นอินเทอ ร์เฟซใน Java ที่ช่วยให้สามารถเรียงลำดับออบเจ็กต์แบบกำหนดเองได้ มีวิธีกำหนดลำดับขององค์ประกอบตามคุณลักษณะหรือคุณสมบัติเฉพาะ ด้วยการใช้ อินเทอร์เฟ ซ Comparatorและแทนที่เมธอดcomparison ()เราสามารถระบุได้ว่าองค์ประกอบต่างๆ ควรเรียงลำดับในTreeSet อย่างไรการสร้าง TreeSet ด้วยตัวเปรียบเทียบแบบกำหนดเอง
ในการสร้างTreeSetด้วยตัวเปรียบเทียบแบบกำหนดเอง เราจำเป็นต้องจัดเตรียมตัวเปรียบเทียบเป็นอาร์กิวเมนต์เมื่อสร้างอินสแตนซ์TreeSet ลองดูตัวอย่าง: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());
}
}
ในโค้ดข้างต้น เราสร้างTreeSetที่เรียกว่า name พร้อมด้วยตัวเปรียบเทียบแบบกำหนดเองที่เรียกว่าLengthComparator lengthComparator เปรียบเทียบความยาวของสองสตริงและเรียงลำดับตามนั้น ด้วยเหตุนี้TreeSet จะถูกจัดเรียงตามความ ยาว ของสตริง ทำให้เราได้ผลลัพธ์[Ivy, Rick, David, Johnny]
ตัวอย่างของการเรียงลำดับ TreeSet โดยใช้ตัวเปรียบเทียบ
นอกจากการสร้างTreeSetด้วยตัวเปรียบเทียบแบบกำหนดเองแล้ว เรายังสามารถใช้ตัวเปรียบเทียบเพื่อเรียงลำดับ TreeSetชั่วคราวโดยไม่ต้องแก้ไขลำดับตามธรรมชาติ ลองดูตัวอย่าง: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]
}
}
ในโค้ดข้างต้น เราสร้างTreeSetที่เรียกว่าชื่อและเพิ่มองค์ประกอบบางอย่าง จากนั้นเราจะสร้างTreeSet ใหม่ ที่เรียกว่าsortedNamesพร้อมด้วยตัวเปรียบเทียบที่กำหนดเองComparator.reverseOrder( ) โดยการเพิ่มองค์ประกอบทั้งหมดจากชื่อเดิมTreeSetไปยังsortedNames เรา จะ ได้รับเวอร์ชันที่เรียงลำดับชั่วคราวของTreeSet
การเปรียบเทียบ TreeSet กับโครงสร้างข้อมูลอื่น
การเปรียบเทียบ TreeSet กับ HashSet
ทั้งTreeSetและHashSetเป็นการใช้งานของSet interface ใน Java อย่างไรก็ตามมีความแตกต่างที่สำคัญระหว่างกัน TreeSet : TreeSetจัดเก็บองค์ประกอบที่ไม่ซ้ำกันตามลำดับการจัดเรียง ใช้แผนผังการค้นหาแบบไบนารีที่ปรับสมดุลในตัวเอง (โดยปกติจะเป็นแผนผังสีแดง-ดำ) เพื่อรักษาลำดับการเรียงลำดับ ส่งผลให้เกิดความซับซ้อนของเวลาลอการิทึมสำหรับการดำเนินการ เช่น การแทรก การลบ และการค้นหา TreeSetมีประสิทธิภาพในการรักษาคอลเลกชันที่เรียงลำดับและดำเนินการตามช่วง อย่างไรก็ตาม มีค่าใช้จ่ายหน่วยความจำสูงกว่าเนื่องจากโครงสร้างแบบต้นไม้ และไม่อนุญาตให้มีองค์ประกอบที่เป็นโมฆะ HashSet : HashSetจัดเก็บองค์ประกอบที่ไม่ซ้ำกันในลักษณะที่ไม่เรียงลำดับโดยใช้รหัสแฮชและแฮชได้ภายใน โดยให้ความซับซ้อนของเวลาคงที่สำหรับการดำเนินการพื้นฐาน เช่น การแทรก การลบ และการค้นหา HashSetมีประสิทธิภาพสำหรับการค้นหาองค์ประกอบอย่างรวดเร็ว และไม่ได้กำหนดโอเวอร์เฮดหน่วยความจำเพิ่มเติมเพื่อรักษาลำดับ อย่างไรก็ตาม ไม่รับประกันการเรียงลำดับองค์ประกอบโดยเฉพาะเมื่อใดควรใช้ TreeSet:
- เมื่อคุณต้องการรักษาองค์ประกอบต่างๆ ตามลำดับโดยอัตโนมัติ
- เมื่อคุณต้องการการดำเนินการตามช่วงหรือต้องการค้นหาองค์ประกอบภายในช่วงเฉพาะอย่างมีประสิทธิภาพ
- เมื่อไม่อนุญาตให้มีองค์ประกอบที่ซ้ำกันและความเป็นเอกลักษณ์จึงเป็นสิ่งสำคัญ
- เมื่อคุณยินดีที่จะแลกการใช้หน่วยความจำที่สูงขึ้นเล็กน้อยเพื่อประโยชน์ของการดำเนินการเรียงลำดับและช่วงอัตโนมัติ
การเปรียบเทียบ TreeSet กับ ArrayList
ArrayListคือการใช้งานอาร์เรย์แบบไดนามิกใน Java นี่คือความแตกต่างที่สำคัญระหว่างTreeSetและArrayList :- TreeSet : TreeSetจัดเก็บองค์ประกอบที่ไม่ซ้ำกันตามลำดับการจัดเรียง ให้การดำเนินการที่มีประสิทธิภาพสำหรับการรักษาคอลเลกชันที่เรียงลำดับและดำเนินการค้นหาตามช่วง มีความซับซ้อนของเวลาลอการิทึมสำหรับการดำเนินการ TreeSetไม่เหมาะสำหรับการเข้าถึงแบบสุ่มหรือการรักษาลำดับการแทรก
- ArrayList : ArrayListจัดเก็บองค์ประกอบตามลำดับการแทรก ช่วยให้เข้าถึงองค์ประกอบแบบสุ่มได้อย่างรวดเร็วโดยใช้ดัชนี มีความซับซ้อนด้านเวลาคงที่สำหรับการดำเนินการส่วนใหญ่เมื่อเข้าถึงองค์ประกอบตามดัชนี อย่างไรก็ตาม มีความซับซ้อนของเวลาเชิงเส้นในการแทรกหรือลบองค์ประกอบออกจากตรงกลางรายการ เนื่องจากต้องมีการเปลี่ยนองค์ประกอบ
เมื่อใดที่ควรพิจารณาโครงสร้างข้อมูลอื่นๆ
- หากไม่จำเป็นต้องรักษาองค์ประกอบตามลำดับที่จัดเรียง และคุณต้องการการค้นหาองค์ประกอบที่รวดเร็วหรือคอลเลกชันที่ไม่เรียงลำดับHashSetอาจเป็นตัวเลือกที่ดีกว่า
- หากคุณต้องการเข้าถึงองค์ประกอบแบบสุ่มบ่อยครั้งตามดัชนีหรือต้องรักษาลำดับการแทรกArrayListน่าจะเหมาะสมกว่า
GO TO FULL VERSION