TreeSet ใน Java

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น่าจะเหมาะสมกว่า