تحليل زمن تشغيل الخرائط المنفذة باستخدام شجرة بحث ثنائية TreeMap في جافا

سنناقش في هذه المقالة تنفيذًا جديدًا للواجهة Map يُعرَف باسم شجرة البحث الثنائية binary search tree. يشيع استخدام هذا التنفيذ عند الحاجة إلى الاحتفاظ بترتيب العناصر.

ما هي مشكلة التعمية hashing؟

يُفترَض أن تكون على معرفةٍ بالواجهة Map، وبالصنف المُنفِّذ لها HashMap الذي تُوفِّره جافا. إذا كنت قد قرأت مقالة تحسين أداء الخرائط المُنفَّذة باستخدام التعمية التي نفّذنا بها نفس الواجهة باستخدام جدول hash table، فيُفترَض أنك تَعرِف الكيفية التي يَعمَل بها الصنف HashMap، والسببَ الذي لأجله تَستغرِق توابع ذلك التنفيذ زمنًا ثابتًا.

يشيع استخدام الصنف HashMap بفضل كفاءته العالية، ولكنه مع ذلك ليس التنفيذ الوحيد للواجهة Map، فهناك أسبابٌ عديدةٌ قد تدفعك لاختيار تنفيذٍ آخرَ، منها:

قد تستغرق عملية حساب شيفرة التعمية زمنًا طويلًا. فعلى الرغم من أن عمليات الصنف HashMap تستغرق زمنًا ثابتًا، فقد يكون ذلك الزمن كبيرًا.
تَعمَل التعمية بشكلٍ جيّدٍ فقط عندما تُوزِّع دالةُ التعميةِ hash function المفاتيحَ بالتساوي على الخرائط الفرعية، ولكنّ تصميمَ دوالِّ التعمية لا يُعدّ أمرًا سهلًا، فإذا احتوت خريطةٌ فرعيّةٌ معيّنةٌ على مفاتيحَ كثيرةٍ، تقل كفاءة الصنف HashMap.
لا تُخزَّن المفاتيح في الجدول وفقًا لترتيبٍ معيّنٍ، بل قد يتغير ترتيبها عند إعادة ضبط حجم الجدول وإعادة حساب شيفرات التعمية للمفاتيح. بالنسبة لبعض التطبيقات، قد يكون الحفاظ على ترتيب المفاتيح ضروريًا أو مفيدًا على الأقل.

من الصعب حل كل تلك المشكلات في الوقت نفسه، ومع ذلك، تُوفِّر جافا التنفيذ TreeMap الذي يُعالِج بعضًا منها:

لا يَستخدِم ذلك الصنفُ دالّةَ تعميةٍ، وبالتالي، يتجنَّب الزمن الإضافي اللازم لحساب شيفرات التعمية، كما يُجنّبُنا صعوباتِ اختيار دالّةِ تعميةٍ مناسبة.
تُخزَّن المفاتيح في الصنف TreeMap بهيئة شجرةِ بحثٍ ثنائيّةٍ، مما يُسهِّل من اجتياز المفاتيح وفقًا لترتيبٍ معيّنٍ وبزمنٍ خطّي.
يتناسب زمن تنفيذ غالبيّة توابع الصنف TreeMap مع log(n)‎، والتي رغم أنها ليست بكفاءة الزمن الثابت، ولكنها ما تزال جيدةً جدًا.

سنشرح طريقة عمل أشجار البحث الثنائية في القسم التالي ثم سنستخدِمها لتنفيذ الواجهة Map، وأخيرًا، سنُحلّل أداء التوابعِ الأساسيّةِ في الخرائط المُنفَّذة باستخدام شجرة.

أشجار البحث الثنائية

شجرة البحث الثنائية عبارةٌ عن شجرةٍ تحتوي كلُّ عقدةٍ فيها على مفتاحٍ، كما تتوفّر فيها "خاصية BST" التي تنص على التالي:

إذا كان لأي عقدةٍ أبٍ عقدةٌ ابنةٌ يسرى، فلا بُدّ أن تكون قيم جميع المفاتيح الموجودة في الشجرة الفرعية اليسرى أصغرَ من قيمة مفتاح تلك العقدة.
إذا كان لأي عقدةٍ أبٍ عقدةٌ ابنةٌ يمنى، فلا بُدّ أن تكون قيم جميع المفاتيح الموجودة في الشجرة الفرعية اليمنى أكبرَ من قيمة مفتاح تلك العقدة.

تَعرِض الصورة السابقة شجرة أعدادٍ صحيحةٍ تُحقِّق الشروطَ السابقة. هذه الصورة مأخوذةٌ من مقالةِ ويكيبيديا موضوعها أشجار البحث الثنائية، والتي قد تفيدك لحل هذا التمرين.

لاحِظ أن مفتاح عقدة الجذر يساوي 8. يُمكِنك التأكّد من أن مفاتيح العقد الموجودة على يسار عقدة الجذر أقلّ من 8 بينما مفاتيح العقد الموجودة على يمينها أكبرَ من 8. تأكّد من تحقّق نفس الشرط للعقد الأخرى.

لا يَستغرِق البحث عن مفتاحٍ ما ضمن شجرةِ بحثٍ ثنائيّةٍ زمنًا طويلًا، لأنك غير مُضطرّ للبحث في كامل الشجرة، وإنما عليك أن تبدأ من جذر الشجرة، ومن ثمّ، تُطبِّق الخوارزميةَ التالية:

افحص قيمة المفتاح الهدفtarget الذي تبحث عنه وطابقه مع قيمة مفتاح العقدة الحالية. فإذا كانا متساويين، فقد انتهيت بالفعل.
أمّا إذا كان المفتاح target أصغرَ من المفتاح الحاليِّ، ابحث في الشجرة الموجودة على اليسار، فإذا لم تكن موجودةً، فهذا يَعنِي أن المفتاح target غيرُ موجودٍ في الشجرة.
وأمّا إذا كان المفتاح target أكبرَ من المفتاح الحاليِّ، ابحث في الشجرة الموجودة على اليمين. فإذا لم تكن موجودة، فهذا يَعنِي أنّ المفتاح target غير موجود في الشجرة.

يَعنِي ما سبق أنك مضطرٌّ للبحث في عقدةٍ ابنة واحدةٍ فقط لكل مستوىً ضمن الشجرة. فعلى سبيل المثال، إذا كنت تبحث عن مفتاح target قيمته تساوي 4 في الرسمة السابقة، فعليك أن تبدأ من عقدة الجذر التي تحتوي على المفتاح 8، ولأن المفتاح المطلوب أقلَّ من 8، فستذهب إلى اليسار، ولأنه أكبر من 3، فستذهب إلى اليمين، ولأنه أقل من 6، فستذهب إلى اليسار، ثم ستعثر على المفتاح الذي تبحث عنه.

تطلّب البحث عن المفتاح في المثال السابق 4 عملياتِ موازنةٍ رغم أنّ الشجرة تحتوي على 9 مفاتيح. يتناسب عدد الموازنات المطلوبة في العموم مع ارتفاع الشجرة وليس مع عدد المفاتيح الموجودة فيها.

ما الذي نستنتجه من ذلك بخصوص العلاقة بين ارتفاع الشجرة h وعدد العقد n؟ إذا بدأنا بارتفاعٍ قصيرٍ وزدناه تدريجيًّا، فسنحصل على التالي:

إذا كان ارتفاع الشجرة h يساوي 1، فإن عدد العقد n ضمن تلك الشجرة يساوي 1.
وإذا كان ارتفاع الشجرة h يساوي 2، فيُمكِننا أن نضيف عقدتين أُخرَيَيْنِ، وبالتالي، يصبح عدد العقد n في الشجرة مساويًا للقيمة 3.
وإذا كان ارتفاع الشجرة h يساوي 3، فيُمكِننا أن نضيف ما يصل إلى أربعِ عقدٍ أخرى، وبالتالي، يصبح عدد العقد n مساويًا للقيمة 7.
وإذا كان ارتفاع الشجرة h يساوي 4، يُمكِننا أن نضيف ما يصل إلى ثماني عقدٍ أخرى، وبالتالي، يصبح عدد العقد n مساويًا للقيمة 15.

ربما لاحظت النمط المشترك بين تلك الأمثلة. إذا رقَّمنا مستويات الشجرة تدريجيًّا من 1 إلى h، فإن عدد العقد في أيّ مستوىً i يَصِل إلى 2^i-1 كحدٍّ أقصى، وبالتالي، يكون عددُ العقدِ الإجماليُّ في عدد h من المستويات هو 2^h-1. إذا كان:

n = 2^h - 1

بتطبيق لوغاريتم الأساس 2 على طرفي المعادلة السابقة، نحصل على التالي:

log₂ n ≈ h

إذًا، يتناسب ارتفاع الشجرة مع log(n)‎ إذا كانت الشجرة ممتلئةً؛ أي إذا كان كل مستوىً فيها يحتوي على العدد الأقصى المسموح به من العقد.

وبالتالي، يتناسب زمنُ البحثِ عن مفتاحٍ ضمن شجرةِ بحثٍ ثنائيّةٍ مع log(n)‎. يُعدّ ذلك صحيحًا سواءٌ أكانت الشجرةُ ممتلئة كلّيًّا أم جزئيًا، ولكنه ليس صحيحًا في المطلق، وهو ما سنراه لاحقًا.

يُطلَق على الخوارزميات التي تَستغرِق زمنًا يتناسب مع log(n)‎ اسم "خوارزمية لوغاريتمية"، وتنتمي إلى ترتيب النمو O(log(n))‎.

تمرين 10

ستكتب في هذا التمرين تنفيذًا للواجهة Map باستخدام شجرةِ بحثٍ ثنائيّةٍ.

انظر إلى التعريفِ المبدئيِّ للصنف MyTreeMap:

public class MyTreeMap<K, V> implements Map<K, V> {

    private int size = 0;
    private Node root = null;

يحتفظ متغيّرُ النسخةِ size بعدد المفاتيح بينما يحتوي root على مرجع reference يشير إلى عقدة الجذر الخاصّةِ بالشجرة. إذا كانت الشجرة فارغةً، يحتوي root على القيمة null وتكون قيمة size مساويةً للصفر.

انظر إلى الصنف Node المُعرَّف داخل الصنف MyTreeMap:

    protected class Node {
        public K key;
        public V value;
        public Node left = null;
        public Node right = null;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

تحتوي كل عقدةٍ على زوج مفتاح/قيمة وعلى مراجعَ تشير إلى العقد الأبناء left و right. قد تكون إحداهما أو كلتاهما فارغة أي تحتوي على القيمة null.

من السهل تنفيذ بعض توابع الواجهة Map مثل size و clear:

    public int size() {
        return size;
    }

    public void clear() {
        size = 0;
        root = null;
    }

من الواضح أن التابع size يَستغرِق زمنًا ثابتًا.

قد تظن للوهلة الأولى أن التابع clear يستغرق زمنًا ثابتًا، ولكن فكر بالتالي: عندما تُضبَط قيمة root إلى القيمة null، يستعيد كانسُ المهملات garbage collector العقدَ الموجودة في الشجرة ويَستغرِق لإنجاز ذلك زمنًا خطيًا. هل ينبغي أن يُحسَب العمل الذي يقوم به كانس المهملات؟ ربما.

ستكتب في القسم التالي تنفيذًا لبعض التوابع الأخرى لا سيّما التابعين الأهمّ get و put.

تنفيذ الصنف TreeMap

ستجد ملفات الشيفرة التالية في مستودع الكتاب:

MyTreeMap.java: يحتوي على الشيفرة المُوضَّحة في الأعلى مع تصورٍ مبدئيٍّ للتوابع غير المكتملة.
MyTreeMapTest.java : يحتوي على اختبارات وحدةٍ للصنف MyTreeMap.

نفِّذ الأمر ant build لتصريف ملفات الشيفرة، ثم نفِّذ الأمر ant MyTreeMapTest. قد تفشل بعض الاختبارات لأنّ هناك بعض التوابع التي ينبغي عليك إكمالها أولًا.

وفَّرنا تصورًا مبدئيًا للتابعين get و containsKey. يَستخدِم كلاهما التابع findNode المُعرَّف باستخدام المُعدِّل private، لأنه ليس جزءًا من الواجهة Map. انظر إلى بداية تعريفه:

    private Node findNode(Object target) {
        if (target == null) {
            throw new IllegalArgumentException();
        }

        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) target;

        // TODO: FILL THIS IN!
        return null;
    }

يشير المعامل target إلى المفتاح الذي نبحث عنه. إذا كانت قيمة target تساوي null، يُبلِّغ التابع findNode عن اعتراضٍ exception. في الواقع، بإمكان بعض تنفيذات الواجهة Map معالجة الحالات التي تكون فيها قيمة المفتاح فارغة، ولكن لأننا في هذا التنفيذ نَستخدِم شجرة بحثٍ ثنائيّةٍ، فلا بُدّ أن نتمكّن من موازنةِ المفاتيح، ولذلك، يُشكِّل التعامل مع القيمة null مشكلةً، ولذا ولكي نُبسِّط الأمور، لن نَسمَح لهذا التنفيذ باستخدام القيمة null كمفتاح.

تُوضِّح الأسطر التالية كيف يمكِننا أن نوازن قيمة المفتاح target مع قيمة مفتاحٍ ضمن الشجرة. تشير نسخةُ التابعين get و containsKey إلى أن المُصرِّف يتعامل مع target كما لو أنه ينتمي إلى النوع Object، ولأننا نريد موازنته مع المفاتيح، فإننا نحوِّل نوع target إلى النوع Comparable<? super K>‎ لكي يُصبِح قابلًا للموازنة مع كائنٍ من النوع K أو أيٍّ من أصنافه الأعلى superclass. يُمكِنك قراءة المزيد عن أنواع محارف البدل (باللغة الإنجليزية).

ليس المقصودُ من هذا التمرين احترافَ التعامل مع نظام الأنواع في لغة جافا، فدورك فقط هو أن تُكمِل التابع findNode. إذا وجد ذلك التابع عقدةً تحتوي على قيمة target كمفتاح، فعليه أن يعيدها، أما إذا لم يجدها، فعليه أن يعيد القيمة null. ينبغي أن تنجح اختبارات التابعين get و containsKey بعد أن تنتهي من إكمال هذا التابع.

اقتباس

ملحوظة: ينبغي للحل الخاص بك أن يبحث في مسارٍ واحدٍ فقط ضمن الشجرة لا أن يبحث في كامل الشجرة، أي سيَستغرِق زمنًا يتناسب مع ارتفاع الشجرة.

والآن، عليك أن تُكمِل التابع containsValue، ولمساعدتك على ذلك، وفَّرنا التابع المساعد equals الذي يُوازِن بين قيمة target وقيمة مفتاحٍ معيّنٍ. على العكس من المفاتيح، قد لا تكون القيم المُخزَّنة في الشجرة قابلةً للموازنة، وبالتالي، لا يُمكِننا أن نَستخدِم معها التابع compareTo، وإنما علينا أن نَستدعِيَ التابعَ equals بالمتغير target.

بخلاف التابع findNode، سيضطرّ التابع containsValue للبحث في كامل الشجرة، أي يتناسب زمن تشغيله مع عدد المفاتيح n وليس مع ارتفاع الشجرة h.

والآن، أكمل متنَ التابع put. وفَّرنا له شيفرةً مبدئيةً تعالج الحالات البسيطة فقط:

    public V put(K key, V value) {
        if (key == null) {
            throw new IllegalArgumentException();
        }
        if (root == null) {
            root = new Node(key, value);
            size++;
            return null;
        }
        return putHelper(root, key, value);
    }

    private V putHelper(Node node, K key, V value) {
        // TODO: Fill this in.
    }

إذا حاولت استخدَام القيمة الفارغة null كمفتاحٍ، سيُبلّغ put عن اعتراض؛ وإذا كانت الشجرة فارغةً، سيُنشِئ التابع put عقدةً جديدةً، ويُهيِّئُ المتغير root المُعرَّف فيها؛ أما إذا لم تكن فارغةً، فإنه يَستدعِي التابع putHelper المُعرَّف باستخدام المُعدِّل private لأنه ليس جزءًا من الواجهة Map.

أكمل متنَ التابع putHelper واجعله يبحث ضمن الشجرة وفقًا لما يلي:

إذا كان المفتاح key موجودًا بالفعل ضمن الشجرة، عليه أن يَستبدِل القيمة الجديدة بالقيمة القديمة، ثم يعيدها.
إذا لم يكن المفتاح key موجودًا في الشجرة، فعليه أن يُنشِىء عقدةً جديدةً، ثم يضيفها إلى المكان الصحيح، وأخيرًا، يعيد القيمة null.

ينبغي أن يَستغرِق التابع put زمنًا يتناسب مع ارتفاع الشجرة h وليس مع عدد العناصر n. سيكون من الأفضل لو بحثت في الشجرة مرةً واحدةً فقط، ولكن إذا كان البحث فيها مرّتين أسهلَ بالنسبة لك، فلا بأس. سيكون التنفيذ أبطأ، ولكنّه لن يؤثر على ترتيب نموه.

وأخيرًا، عليك أن تُكمِل متن التابع keySet. يعيد ذلك التابع -وفقًا لـللتوثيق (باللغة الإنجليزية)- قيمة من النوع Set بإمكانها المرور عبر جميع مفاتيح الشجرة بترتيبٍ تصاعديٍّ وفقًا للتابع compareTo. كنا قد اِستخدَمنا الصنف HashSet في مقالة استخدام خريطة ومجموعة لبناء مُفهرِس Indexer. يُعدّ ذلك الصنف تنفيذًا للواجهة Set ولكنه لا يحافظ على ترتيب المفاتيح. في المقابل، يتوفَّر التنفيذ LinkedHashSet الذي يحافظ على ترتيب المفاتيح.

يُنشِئ التابع keySet قيمةً من النوع LinkedHashSet ويعيدها كما يلي:

    public Set<K> keySet() {
        Set<K> set = new LinkedHashSet<K>();
        return set;
    }

عليك أن تُكمِل هذا التابع بحيث تجعلُه يضيفُ المفاتيح من الشجرة إلى المجموعة set بترتيبٍ تصاعديّ.

اقتباس

تلميح: قد تحتاج إلى كتابةٍ تابعٍ مساعدٍ، وقد ترغب بجعله تعاوديًّا recursive.

ينبغي أن تنجح جميع الاختبارات بعد أن تنتهي من إكمال هذا التابع. سنَعرِض حل هذا التمرين ونفحص أداء التوابع الأساسية في الصنف في مقالٍ آخر من هذه السلسلة.

ترجمة -بتصرّف- للفصل Chapter 12: TreeMap من كتاب Think Data Structures: Algorithms and Information Retrieval in Java.