TreeSet في جافا

توفر Java مجموعة واسعة من هياكل البيانات للعمل بكفاءة مع مجموعات العناصر. إحدى هياكل البيانات هذه هي TreeSet، وهو تطبيق لشجرة حمراء وسوداء في Java. يحتفظ TreeSet بترتيب مفروز لتخزين العناصر الفريدة. قد يجد المبتدئون أن استخدام فئة Java TreeSet صعبًا بعض الشيء في البداية. في هذه المقالة، سنتعرف على كيفية استخدام TreeSet ، مع شرح مفاهيمه الأساسية وتقديم أمثلة التعليمات البرمجية لمساعدتك على بدء دمج TreeSet في مشاريع Java الخاصة بك.

بنية TreeSet: شجرة حمراء-سوداء

كما ذكرنا من قبل، يتم تنفيذ بنية فئة Java TreeSet كشجرة بحث ثنائية ذاتية التوازن تُعرف باسم شجرة Red-Black. دعنا نشرح ما هذا... تمثل الشجرة ذات اللون الأحمر والأسود بنية بيانات بحث ثنائية متوازنة تُستخدم عادةً لتخزين البيانات المصنفة وتنظيمها. تستمد اسمها من الخصائص التي تحافظ على توازنها:

• كل عقدة في الشجرة حمراء أو سوداء.
• جذر الشجرة ذات اللون الأحمر والأسود دائمًا ما يكون أسود.
• كافة العقد الطرفية (العقد 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.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 : استخدام المكرر واستخدام حلقة for-each المحسنة. يوفر 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] .

تسمح لنا طرق البحث القائمة على النطاق باسترداد مجموعات فرعية من العناصر بناءً على معايير محددة، مما يوفر المرونة في العمل مع البيانات المصنفة.

المقارنة في TreeSet: الفرز باستخدام معايير مخصصة

باستثناء الترتيب الطبيعي، يمكنك استخدام Comparator مخصص لفرز TreeSet . في هذا القسم، سوف نتعمق في مفهوم المقارنة ودورها في TreeSet . سوف نستكشف كيفية إنشاء TreeSet باستخدام مقارنة مخصصة ونقدم أمثلة التعليمات البرمجية لتوضيح فرز TreeSet بناءً على معايير محددة.

ما هو المقارن؟

المقارنة عبارة عن واجهة في Java تتيح فرزًا مخصصًا للكائنات. فهو يوفر طريقة لتحديد ترتيب العناصر بناءً على سمات أو خصائص محددة. من خلال تطبيق واجهة المقارنة وتجاوز طريقة المقارنة () الخاصة بها ، يمكننا تحديد كيفية فرز العناصر في 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 تسمى الأسماء مع مقارنة مخصصة تسمى 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 في Java. ومع ذلك، هناك اختلافات كبيرة بينهما. TreeSet : يقوم TreeSet بتخزين العناصر الفريدة بترتيب فرزها. ويستخدم شجرة بحث ثنائية ذاتية التوازن (عادةً شجرة حمراء وسوداء) للحفاظ على الترتيب المفرز، مما يؤدي إلى تعقيد الوقت اللوغاريتمي لعمليات مثل الإدراج والحذف والبحث. يعتبر TreeSet فعالاً في الحفاظ على المجموعة التي تم فرزها وتنفيذ العمليات المستندة إلى النطاق. ومع ذلك، فهو يحتوي على حمل أعلى للذاكرة بسبب بنية الشجرة ولا يسمح بالعناصر الفارغة. HashSet : يقوم HashSet بتخزين العناصر الفريدة بطريقة غير مرتبة باستخدام رموز التجزئة والتجزئة داخليًا. يوفر تعقيدًا زمنيًا ثابتًا للعمليات الأساسية مثل الإدراج والحذف والبحث. يعد HashSet فعالاً للبحث السريع عن العناصر ولا يفرض أي حمل إضافي للذاكرة للحفاظ على النظام. ومع ذلك، فهو لا يضمن أي ترتيب محدد للعناصر.

متى تستخدم TreeSet:

• عندما تحتاج إلى الاحتفاظ بالعناصر بترتيب مفروز تلقائيًا.
• عندما تحتاج إلى عمليات تعتمد على النطاق أو تحتاج إلى العثور على عناصر ضمن نطاق معين بكفاءة.
• عندما لا يُسمح بالعناصر المكررة ويكون التفرد ضروريًا.
• عندما تكون على استعداد لاستبدال استخدام ذاكرة أعلى قليلًا مقابل فوائد الفرز التلقائي وعمليات النطاق.

مقارنة TreeSet مع ArrayList

ArrayList هو تطبيق صفيف ديناميكي في Java. فيما يلي الاختلافات الرئيسية بين TreeSet و ArrayList :

• TreeSet : يقوم TreeSet بتخزين العناصر الفريدة بترتيب مفروز، مما يوفر عمليات فعالة للحفاظ على مجموعة مفروزة وإجراء عمليات بحث قائمة على النطاق. لديها تعقيد زمني لوغاريتمي للعمليات. TreeSet غير مناسب للوصول العشوائي أو الحفاظ على ترتيب الإدراج.
• ArrayList : يقوم ArrayList بتخزين العناصر بترتيب الإدراج، مما يوفر وصولاً عشوائيًا سريعًا إلى العناصر باستخدام الفهارس. لديها تعقيد زمني ثابت لمعظم العمليات عند الوصول إلى العناصر حسب الفهرس. ومع ذلك، فهي تحتوي على تعقيد زمني خطي لإدراج العناصر أو إزالتها من منتصف القائمة، لأنها تتطلب تغيير العناصر.

متى يجب النظر في هياكل البيانات الأخرى

• إذا لم يكن الحفاظ على العناصر بترتيب مفروز مطلوبًا، وكنت بحاجة إلى بحث سريع عن العناصر أو مجموعة غير مرتبة، فقد يكون HashSet خيارًا أفضل.
• إذا كنت تحتاج إلى وصول عشوائي متكرر إلى العناصر حسب الفهرس أو تحتاج إلى الحفاظ على ترتيب الإدراج، فسيكون ArrayList أكثر ملاءمة.