TreeSet ב-Java

Java מספקת סט עצום של מבני נתונים לעבודה יעילה עם אוספי אלמנטים. מבנה נתונים אחד כזה הוא TreeSet, מימוש של עץ אדום-שחור ב-Java. TreeSet שומר על סדר ממוין לאחסון אלמנטים ייחודיים. מתחילים עשויים למצוא את השימוש בשיעור Java TreeSet מעט מאתגר בתחילה. במאמר זה, אנו הולכים להבין כיצד להשתמש ב-TreeSet , להסביר את מושגי הליבה שלו ולספק דוגמאות קוד שיעזרו לך להתחיל לשלב את TreeSet בפרויקטי Java שלך.

מבנה TreeSet: עץ אדום-שחור

כפי שציינו קודם, מבנה המחלקה של Java TreeSet מיושם כעץ חיפוש בינארי המאזן עצמי המכונה עץ אדום-שחור. בואו נסביר מה זה... עץ אדום-שחור מייצג מבנה נתוני חיפוש בינארי מאוזן המשמש בדרך כלל לאחסון וארגון נתונים ממוינים. הוא שואב את שמו מהמאפיינים השומרים על האיזון שלו:

• כל צומת בעץ אדום או שחור.
• שורש העץ האדום-שחור תמיד שחור.
• כל צמתי העלים (צמתי NIL או קישורים אפסים) שחורים.
• אם צומת של העץ אדום, אז ילדיו שחורים.
• כל נתיב פשוט מצומת לצמתים צאצאים שלו מכיל מספר שווה של צמתים שחורים.

עצים אדומים-שחורים מציגים ביצועים יעילים עבור פעולות הכנסה, מחיקה וחיפוש אלמנטים על ידי הבטחת איזון. זה מבטיח שגובה העץ יישאר פרופורציונלי ללוגריתם של מספר הצמתים שהוא מכיל, וכתוצאה מכך מורכבות זמן לוגריתמית לפעולות. עצים אדומים-שחורים מוצאים יישומים רחבים בתחומים שונים, כולל יישום של עצי חיפוש מאוזנים בשפות תכנות, מסדי נתונים (למשל, מבני אינדקס פנימיים), ותרחישים אחרים שבהם נחוצים אחסון יעיל ופעולות על נתונים ממוינים.

תכונות וחולשות של TreeSet

TreeSet מספק מספר תכונות מפתח שהופכות אותו לכלי בעל ערך לניהול אוספים של אובייקטים בצורה ממוינת. יתרונות:

• תחזוקה אוטומטית של אלמנטים בסדר ממוין. בעת הוספה או הסרה של אלמנטים, מבנה העץ מתכוונן כדי לשמור אותם ממוינים. זה מבטל את הצורך במיון ידני ומספק גישה יעילה בסדר עולה או יורד.
• פעולות חיפוש, הוספה ומחיקה יעילים. הוא משתמש במבנה עץ חיפוש בינארי, המאפשר פעולות אלה במורכבות זמן של O(log N) . כאן N הוא מספר האלמנטים.
• TreeSet מבטיח את הייחודיות של אלמנטים על ידי ניצול הסדר הטבעי שלהם או Comparator מותאם אישית . זה שימושי כאשר עובדים עם אוספים הדורשים אלמנטים נפרדים.

מגבלות:

• מעט יותר איטי מה- HashSet בגלל שמירה על סדר ממוין.
• אינו מאפשר רכיבים null, מכיוון שהוא מסתמך על סדר טבעי או Comparator מותאם אישית להשוואת רכיבים.

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 שומר אוטומטית על אלמנטים בסדר ממוין. עם זאת, אנו יכולים להתאים אישית את התנהגות המיון על ידי מתן Comparator במהלך יצירת 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 . אנו יכולים להשתמש באיטרטור או להשתמש בלולאה המשופרת עבור כל לולאה. בואו נראה דוגמאות לשתי הגישות:

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 : שימוש באיטרטור ושימוש בלולאה המשופרת עבור כל לולאה. 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 שנקרא מספרים ומוסיפים כמה אלמנטים. לאחר מכן אנו מדגים חיפושים מבוססי טווח באמצעות השיטות subSet() , headSet() ו- tailSet() .

• קבוצת המשנה TreeSet מכילה אלמנטים בין 3 (כולל) ל-8 (בלעדי), שהם [3, 5, 7] .
• ה- headSet TreeSet מכיל אלמנטים פחות מ-6, שהם [1, 3, 5] .
• ה- tailSet TreeSet מכיל אלמנטים הגדולים או שווים ל-5, שהם [5, 7, 9] .

שיטות חיפוש המבוססות על טווח מאפשרות לנו לאחזר קבוצות משנה של אלמנטים על סמך קריטריונים ספציפיים, ומספקות גמישות בעבודה עם נתונים ממוינים.

Comparator ב-TreeSet: מיון עם קריטריונים מותאמים אישית

למעט סדר טבעי, אתה יכול להשתמש ב- Comparator מותאם אישית למיון TreeSet . בחלק זה, נעמיק במושג המשווה ותפקידו ב- TreeSet . נחקור כיצד ליצור TreeSet עם משווה מותאם אישית ונספק דוגמאות קוד להדגמת מיון TreeSet על סמך קריטריונים ספציפיים.

מה זה Comparator?

Comparator הוא ממשק ב-Java המאפשר מיון מותאם אישית של אובייקטים . הוא מספק דרך להגדיר את סדר האלמנטים על סמך תכונות או מאפיינים ספציפיים. על ידי הטמעת ממשק Comparator ועקיפה של שיטת compare() שלו , אנו יכולים לציין כיצד יש למיין אלמנטים ב- TreeSet .

יצירת TreeSet עם Comparator מותאם אישית

כדי ליצור 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 בשם שמות עם השוואה מותאמת אישית בשם LengthComparator . LengthComparator משווה את האורך של שתי מחרוזות וממיין אותן בהתאם. כתוצאה מכך, ה- TreeSet ממוין על סמך אורך המחרוזות, נותן לנו את הפלט [Ivy, Rick, David, Johnny] .

דוגמאות למיון TreeSet באמצעות Comparator

מלבד יצירת TreeSet עם משווה מותאם אישית, אנו יכולים גם להשתמש ב-comparator כדי למיין 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 ב-Java. עם זאת, ישנם הבדלים משמעותיים ביניהם. TreeSet : TreeSet מאחסן אלמנטים ייחודיים בסדר ממוין. הוא משתמש בעץ חיפוש בינארי המאזן את עצמו (בדרך כלל עץ אדום-שחור) כדי לשמור על הסדר הממוין, וכתוצאה מכך מורכבות זמן לוגריתמית עבור פעולות כמו הכנסה, מחיקה וחיפוש. TreeSet יעיל לשמירה על אוסף ממוין וביצוע פעולות מבוססות טווח. עם זאת, יש לו תקורה של זיכרון גבוה יותר בגלל מבנה העץ ואינו מאפשר אלמנטים null. HashSet : HashSet מאחסן אלמנטים ייחודיים בצורה לא מסודרת באמצעות קודי hash ו-hashable פנימי. הוא מספק מורכבות זמן קבועה עבור פעולות בסיסיות כמו הכנסה, מחיקה וחיפוש. HashSet יעיל לחיפוש אלמנטים מהיר ואינו מטיל תקורה נוספת של זיכרון לשמירה על הסדר. עם זאת, זה לא מבטיח שום סדר ספציפי של אלמנטים.

מתי להשתמש ב-TreeSet:

• כאשר אתה צריך לתחזק אלמנטים בסדר ממוין באופן אוטומטי.
• כאשר אתה זקוק לפעולות מבוססות טווח או שאתה צריך למצוא אלמנטים בטווח מסוים ביעילות.
• כאשר אלמנטים כפולים אינם מותרים והייחודיות חיונית.
• כאשר אתה מוכן לסחור בשימוש בזיכרון מעט גבוה יותר עבור היתרונות של פעולות מיון וטווח אוטומטיים.

השוואת TreeSet עם ArrayList

ArrayList הוא מימוש מערך דינמי ב-Java. להלן ההבדלים העיקריים בין TreeSet ל- ArrayList :

• TreeSet : TreeSet מאחסן אלמנטים ייחודיים בסדר ממוין, ומספק פעולות יעילות לשמירה על אוסף ממוין וביצוע חיפושים מבוססי טווח. יש לו מורכבות זמן לוגריתמית לפעולות. TreeSet אינו מתאים לגישה אקראית או לשמירה על סדר ההכנסה.
• ArrayList : ArrayList מאחסן אלמנטים לפי סדר ההכנסה, ומספק גישה אקראית מהירה לאלמנטים באמצעות מדדים. יש לו מורכבות זמן קבועה עבור רוב הפעולות בעת גישה לאלמנטים לפי אינדקס. עם זאת, יש לו מורכבות זמן ליניארית להכנסה או הסרה של אלמנטים מאמצע הרשימה, מכיוון שהיא דורשת אלמנטים בהסטה.

מתי לשקול מבני נתונים אחרים

• אם לא נדרשת תחזוקה של אלמנטים בסדר ממוין, ואתה צריך חיפוש מהיר של רכיבים או אוסף לא מסודר, ייתכן שה- HashSet תהיה בחירה טובה יותר.
• אם אתה זקוק לגישה אקראית תכופה לאלמנטים לפי אינדקס או שאתה צריך לשמור על סדר ההכנסה, ArrayList יהיה מתאים יותר.