إطار المجموعات

TreeSet والمجموعات المرتّبة

15 دقيقة الدرس 5 من 14

TreeSet والمجموعات المرتّبة

تمنحك HashSet عمليات تحقق سريعة من العضوية لكنها لا تضمن أي ترتيب. أحيانًا تحتاج إلى التفرّد والترتيب المتوقّع في آنٍ واحد — وهذا بالضبط ما توفّره TreeSet. إدراك متى تلجأ إلى TreeSet بدلًا من HashSet خطوةٌ مهمة نحو كتابة كود Java معبّر وفعّال.

ما الذي يقبع تحت غطاء TreeSet

TreeSet<E> هي مجموعة من نوع NavigableSet مبنيّة على شجرة أحمر-أسود (red-black tree). كل إدراج أو حذف يكون بتعقيد O(log n) بدلًا من O(1) التقريبي في المجموعات المبنية على جدول تقطيع. المقايضة هي أن التكرار يزور العناصر دومًا بترتيب تصاعدي مرتّب، ويصبح بالإمكان استخدام مجموعة غنية من توابع التصفح.

تسلسل الواجهات: تُنفّذ TreeSet الواجهة NavigableSet، التي تمتد من SortedSet، التي تمتد من Set. إن احتجت فقط إلى تكرار مرتّب، اكتب نوع المتغير كـ SortedSet. وإن احتجت إلى توابع التصفح (floor وceiling وغيرها)، استخدم NavigableSet.

الترتيب الطبيعي عبر Comparable

عند إنشاء TreeSet دون تمرير مقارِن، تستخدم الترتيب الطبيعي — الترتيب المعرَّف في تنفيذ Comparable<T> الخاص بالعناصر. جميع أنواع المغلّفات في Java كـInteger وString وLocalDate تُنفّذ Comparable بالفعل، لذا يعمل هذا مباشرة:

import java.util.TreeSet;

TreeSet<String> languages = new TreeSet<>();
languages.add("Python");
languages.add("Java");
languages.add("C++");
languages.add("Rust");
languages.add("Java");   // مكرّر — يُتجاهل بصمت

System.out.println(languages);
// الإخراج: [C++, Java, Python, Rust]   (أبجدي، بلا مكرّرات)

بالنسبة لفئاتك الخاصة، تُنفّذ Comparable<T> بتجاوز تابع compareTo. العقد: أعِد رقمًا سالبًا عندما يكون this أصغر من الوسيط، صفرًا عند التساوي، ورقمًا موجبًا عند الكبر.

public class Student implements Comparable<Student> {
    private final String name;
    private final double gpa;

    public Student(String name, double gpa) {
        this.name = name;
        this.gpa  = gpa;
    }

    @Override
    public int compareTo(Student other) {
        // الترتيب الأساسي: GPA تنازلي (الأعلى أولًا)
        int cmp = Double.compare(other.gpa, this.gpa);
        // الترتيب الثانوي: الاسم تصاعديًا لكسر التعادل
        return (cmp != 0) ? cmp : this.name.compareTo(other.name);
    }

    @Override
    public String toString() { return name + "(" + gpa + ")"; }
}

// الاستخدام
TreeSet<Student> ranked = new TreeSet<>();
ranked.add(new Student("Alice",  3.9));
ranked.add(new Student("Bob",    3.7));
ranked.add(new Student("Carol",  3.9));

System.out.println(ranked);
// [Alice(3.9), Carol(3.9), Bob(3.7)]

يجب أن يكون compareTo متوافقًا مع equals. إذا قارن كائنان بنتيجة صفر يجب أن يكونا متساويَين وفق equals() أيضًا — وإلا ستعاملهما TreeSet كمكرّر بينما لن تفعل HashSet، مما يُنتج أخطاءً محيّرة عند تبديل التنفيذات.

عمليات NavigableSet

تكشف TreeSet توابع تصفح قوية لا مقابل لها في HashSet:

first() / last() — أصغر / أكبر عنصر.
floor(e) — أكبر عنصر أصغر من أو يساوي e، أو null.
ceiling(e) — أصغر عنصر أكبر من أو يساوي e، أو null.
lower(e) — أكبر عنصر أصغر تمامًا من e.
higher(e) — أصغر عنصر أكبر تمامًا من e.
headSet(to) / tailSet(from) — عرض للعناصر قبل / من قيمة معيّنة.
subSet(from, to) — عرض حيّ للنطاق [from, to).
pollFirst() / pollLast() — إزالة وإعادة أصغر / أكبر عنصر.

TreeSet<Integer> scores = new TreeSet<>(
    java.util.List.of(55, 72, 88, 91, 64, 78, 91, 99)
);
// {55, 64, 72, 78, 88, 91, 99}  (مرتّب، دون تكرار 91)

System.out.println(scores.first());         // 55
System.out.println(scores.last());          // 99
System.out.println(scores.floor(80));       // 78  (≤ 80)
System.out.println(scores.ceiling(80));     // 88  (≥ 80)
System.out.println(scores.lower(78));       // 72  (أصغر تمامًا من 78)
System.out.println(scores.higher(78));      // 88  (أكبر تمامًا من 78)

// عرض فرعي حيّ — التغييرات على العرض تنعكس في المجموعة الأصلية
var passing = scores.tailSet(60);           // [64, 72, 78, 88, 91, 99]
System.out.println(passing);
passing.remove(64);                         // يُزيل 64 من scores أيضًا
System.out.println(scores);                 // [55, 72, 78, 88, 91, 99]

العروض الفرعية حيّة وليست نسخًا. تُعيد headSet وtailSet وsubSet عروضًا مدعومة. تنتقل التعديلات عبر العرض إلى المجموعة الأصلية والعكس صحيح — مفيد لعمليات الحذف بالنطاق أو التكرار على نطاق دون نسخ.

الترتيب التنازلي

تريد التكرار من الأكبر إلى الأصغر دون كتابة مقارِن مخصص؟ استدعِ descendingSet():

TreeSet<Integer> asc = new TreeSet<>(java.util.List.of(3, 1, 4, 1, 5, 9));
// asc: [1, 3, 4, 5, 9]

var desc = asc.descendingSet();             // عرض مدعوم، لا نسخة
System.out.println(desc);                   // [9, 5, 4, 3, 1]

متى تختار TreeSet بدلًا من HashSet

تحتاج إلى التكرار على العناصر بترتيب مرتّب.
تحتاج إلى استعلامات نطاق (جميع العناصر بين X وY).
تحتاج إلى الحصول على الحد الأدنى أو الأقصى بسرعة.
عناصرك تُنفّذ Comparable (أو تزوّد Comparator).

إن لم ينطبق شيء من هذا، التزم بـHashSet — عملياتها بتعقيد O(1) تتفوق على O(log n) لدى TreeSet في اختبارات العضوية البحتة على نطاق واسع.

الخلاصة

تخزّن TreeSet عناصر فريدة بترتيب مرتّب باستخدام شجرة أحمر-أسود. يعتمد الترتيب الطبيعي على Comparable؛ زوّد Comparator حين تحتاج ترتيبًا مختلفًا أو حين لا يُنفّذ نوع العنصر Comparable. واجهة برمجة التطبيقات NavigableSet — floor وceiling وheadSet وsubSet وغيرها — تجعل عمليات البحث بالنطاق معبّرة وفعّالة. في الدرس التالي سنتناول المكافئ الخرائطي لـTreeSet: وهما TreeMap وLinkedHashMap.