خريطة الشجرة في جافا

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

مقارنة TreeMap وHashMap وLinkedHashMap

التطبيق الأكثر استخدامًا لواجهة الخريطة هو HashMap. إنه سهل الاستخدام ويضمن الوصول السريع إلى البيانات، لذا فهو المرشح الأفضل لحل معظم المشكلات. معظم، ولكن ليس كل شيء. تحتاج في بعض الأحيان إلى تخزين البيانات بطريقة منظمة والقدرة على التنقل خلالها. في هذه الحالة، يأتي تطبيق آخر لواجهة الخريطة (TreeMap) للإنقاذ. تطبق TreeMap واجهة NavigableMap ، التي ترث SortedMap ، والتي بدورها ترث واجهة الخريطة. من خلال تنفيذ واجهات NavigableMap و SortedMap ، تتلقى TreeMap وظائف إضافية غير متوفرة في HashMap، ولكنها تدفع ثمنًا من حيث الأداء. هناك أيضًا فئة LinkedHashMap ، والتي تتيح لك أيضًا تخزين البيانات بترتيب معين (الترتيب الذي تضيفه به إلى الخريطة). لفهم الاختلافات بين هذه الفئات الثلاث، انظر إلى هذا الجدول: كما ترون، هذه الفئات لديها الكثير من القواسم المشتركة، ولكن هناك أيضا العديد من الاختلافات. على الرغم من أن فئة TreeMap هي الأكثر تنوعًا، إلا أنه لا يمكنها دائمًا تخزين قيمة خالية كمفتاح. بالإضافة إلى ذلك، يستغرق الوصول إلى عناصر TreeMap وقتًا أطول. لذا، إذا لم تكن بحاجة إلى تخزين البيانات بترتيب معين، فمن الأفضل استخدام HashMap أو LinkedHashMap .

شجرة حمراء سوداء

ربما لاحظت أنه، تحت الغطاء، يستخدم TreeMap بنية بيانات تسمى شجرة حمراء-سوداء. تخزين البيانات في هذه البنية هو بالضبط ما يوفر ترتيب البيانات. إذن أي نوع من الأشجار هذا؟ دعونا معرفة ذلك! تخيل أنك بحاجة إلى تخزين أزواج سلسلة الأرقام. الأرقام 16، 20، 52، 55، 61، 65، 71، 76، 81، 85، 90، 93، و101 ستكون مفاتيح. إذا قمت بتخزين البيانات في قائمة تقليدية وتحتاج إلى العثور على العنصر الذي يحتوي على المفتاح 101، فستحتاج إلى التنقل بين العناصر الثلاثة عشر للعثور عليه. بالنسبة لـ 13 عنصرًا، هذا ليس مشكلة كبيرة، ولكن عند العمل مع مليون عنصر، سنواجه مشكلات كبيرة. لحل هذه المشاكل، يستخدم المبرمجون هياكل بيانات أكثر تعقيدًا قليلاً. هذا هو المكان الذي تدخل فيه الشجرة ذات اللون الأحمر والأسود إلى المسرح! يبدأ البحث عن عنصر من جذر الشجرة، وهو في حالتنا 61. ثم نقارن قيم العقدة بالقيمة التي نبحث عنها. إذا كانت القيمة لدينا أقل، فإننا نتجه إلى اليسار؛ إذا كان أكبر، فإننا نذهب إلى اليمين. تتكرر هذه العملية حتى نجد القيمة المطلوبة أو نواجه عنصرًا قيمته فارغة (ورقة الشجرة). يتم استخدام الألوان الأحمر والأسود لتبسيط التنقل وموازنة الشجرة. هناك قواعد يجب مراعاتها دائمًا عند بناء شجرة حمراء سوداء:

• يجب أن يكون الجذر أسود.
• يجب أن تكون أوراق الشجرة سوداء.
• يجب أن تحتوي العقدة الحمراء على عقدتين تابعتين باللون الأسود.
• يمكن أن تحتوي العقدة السوداء على عقد فرعية من أي لون.
• يجب أن يحتوي المسار من العقدة إلى أوراقها على نفس العدد من العقد السوداء.
• تتم إضافة العقد الجديدة إلى الأوراق.

إذا نظرت إلى القواعد 3 و4 و5 معًا، فيمكنك فهم كيف يتيح لنا لون العقدة التنقل في الشجرة بسرعة أكبر: المسار عبر العقد السوداء يكون دائمًا أقصر من المسار عبر العقد الحمراء. وبناء على ذلك، يتم تحديد الحجم الإجمالي للشجرة من خلال عدد العقد السوداء، وهو ما يسمى "الارتفاع الأسود". يتم تنفيذ بنية بيانات الشجرة ذات اللون الأحمر والأسود بلغات البرمجة المختلفة. هناك الكثير من تطبيقات Java على الإنترنت، لذلك لن نطيل هنا. بدلاً من ذلك، دعنا نواصل التعرف على وظائف TreeMap.

الأساليب التي تأتي من واجهات SortedMap وNavigableMap

مثل HashMap، يقوم TreeMap بتنفيذ واجهة الخريطة، مما يعني أن TreeMap لديه جميع الأساليب الموجودة في HashMap. لكن TreeMap تنفذ أيضًا واجهات SortedMap و NavigableMap ، وبالتالي تكتسب وظائف إضافية منها. SortedMap عبارة عن واجهة تعمل على توسيع الخريطة وإضافة الأساليب ذات الصلة بمجموعة البيانات التي تم فرزها:

• firstKey() : يُرجع مفتاح العنصر الأول في الخريطة
• lastKey() : يُرجع مفتاح العنصر الأخير
• headMap(K end) : يُرجع خريطة تحتوي على جميع عناصر الخريطة الحالية، من البداية إلى العنصر ذو النهاية الرئيسية
• tailMap(K start) : يُرجع خريطة تحتوي على جميع عناصر الخريطة الحالية، من عنصر البداية إلى النهاية
• subMap(K start, K ​​end) : يُرجع خريطة تحتوي على جميع عناصر الخريطة الحالية، من عنصر البداية إلى العنصر ذو النهاية الرئيسية.

NavigableMap عبارة عن واجهة تعمل على توسيع SortedMap وإضافة طرق للتنقل بين عناصر الخريطة:

• firstEntry() : يُرجع أول زوج من قيمة المفتاح
• lastEntry() : يُرجع آخر زوج من قيمة المفتاح
• pollFirstEntry() : يقوم بإرجاع الزوج الأول وحذفه
• pollLastEntry() : إرجاع الزوج الأخير وحذفه
• CeilingKey(K obj) : يُرجع أصغر مفتاح k أكبر من أو يساوي المفتاح obj. إذا لم يكن هناك مثل هذا المفتاح، فسيتم إرجاع القيمة null
• FloorKey(K obj) : يُرجع أكبر مفتاح k أقل من أو يساوي المفتاح obj. إذا لم يكن هناك مثل هذا المفتاح، فسيتم إرجاع القيمة null
• LowerKey(K obj) : يُرجع أكبر مفتاح k وهو أقل من المفتاح obj. إذا لم يكن هناك مثل هذا المفتاح، فسيتم إرجاع القيمة null
• HigherKey(K obj) : يُرجع أصغر مفتاح k أكبر من المفتاح obj. إذا لم يكن هناك مثل هذا المفتاح، فسيتم إرجاع القيمة null
• CeilEntry(K obj) : يشبه أسلوب CeilKey(K obj)، ويعيد فقط زوجًا من القيمة الرئيسية (أو خاليًا)
• FloorEntry(K obj) : يشبه أسلوب FloorKey(K obj)، ويعيد فقط زوجًا من القيمة الرئيسية (أو خاليًا)
• LowerEntry(K obj) : يشبه أسلوب LowerKey(K obj)، ويعيد فقط زوجًا من القيمة الرئيسية (أو خاليًا)
• HigherEntry(K obj) : يشبه الأسلوب HigherKey(K obj)، ويعيد فقط زوجًا من القيمة الرئيسية (أو خاليًا)
• تنازليKeySet() : يُرجع NavigableSet الذي يحتوي على جميع المفاتيح مرتبة بترتيب عكسي
• تنازليMap () : يُرجع NavigableMap الذي يحتوي على جميع الأزواج مرتبة بترتيب عكسي
• navigableKeySet() : إرجاع كائن NavigableSet الذي يحتوي على كافة المفاتيح بالترتيب الذي تم تخزينها به
• headMap(K UpperBound, boolean incl) : يُرجع خريطة تحتوي على أزواج من البداية إلى عنصر UpperBound. تشير المعلمة incl إلى ما إذا كان سيتم تضمين عنصر UpperBound في الخريطة التي تم إرجاعها
• tailMap(K LowerBound, boolean incl) : وظيفة مشابهة للطريقة السابقة، تُرجع الأزواج فقط من LowerBound إلى النهاية
• subMap(K LowerBound, boolean lowIncl, K UpperBound, boolean HighIncl) : كما هو الحال مع الطرق السابقة، يتم إرجاع الأزواج من LowerBound إلى UpperBound؛ تشير الوسيطتان lowIncl وhighIncl إلى ما إذا كان سيتم تضمين عناصر الحدود في الخريطة الجديدة.

بالإضافة إلى المنشئات المعتادة، لدى TreeMap مُنشئ آخر يقبل مثيل المقارنة. هذه المقارنة مسؤولة عن الترتيب الذي يتم به تخزين العناصر.

أمثلة على TreeMap

قد تبدو هذه الوفرة من الأساليب الإضافية غير ضرورية، لكنها أكثر فائدة بكثير مما قد تدركه للوهلة الأولى. دعونا نستكشف المثال التالي معًا. تخيل أننا نعمل في قسم التسويق في شركة كبيرة، ولدينا قاعدة بيانات للأشخاص الذين نريد عرض الإعلانات عليهم. هناك نوعان من التفاصيل التي يجب وضعها في الاعتبار:

• نحن بحاجة إلى تتبع عدد مرات الظهور لكل شخص
• تختلف خوارزمية عرض الإعلانات للقاصرين.

لنقم بإنشاء فئة "الشخص" ، والتي ستقوم بتخزين جميع المعلومات ذات الصلة بكل شخص:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

نحن ننفذ المنطق في الفئة الرئيسية :

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map) {}
   public static void showAdvertisementToAdult(Map map) {}
}

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