هياكل البيانات 101 استخدام أشجار البحث الثنائية والأشجار المتزنة balanced trees لتنفيذ الخرائط

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

الصنف MyTreeMap

وفَّرنا في المقالة المشار إليها تصوّرًا مبدئيًا للصنف MyTreeMap، وتركنا للقارئ مهمة إكمال توابعه. وسنُكملها الآنَ معًا، ولْنبدأ بالتابع findNode:

private Node findNode(Object target) {
    // some implementations can handle null as a key, but not this one
    if (target == null) {
            throw new IllegalArgumentException();
    }

    // something to make the compiler happy
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) target;

    // the actual search
    Node node = root;
    while (node != null) {
        int cmp = k.compareTo(node.key);
        if (cmp < 0)
            node = node.left;
        else if (cmp > 0)
            node = node.right;
        else
            return node;
    }
    return null;
}

يَستخدِم التابعان containsKey و get التابعَ findNode، ولأنه ليس جزءًا من الواجهة Map، عرَّفناه باستخدام المُعدّل private. يُمثِل المعامل target المفتاحَ الذي نبحث عنه. كنا قد شرحنا الجزء الأول من هذا التابع في المقال المشار إليه:

• لا تُعدّ null قيمةً صالحةً كمفتاحٍ في هذا التنفيذ.
• ينبغي أن نحوِّلَ نوعَ المعاملِ target إلى Comparable قبل أن نَستدعِيَ تابعَه compareTo. اِستخدَمنا أكثر أنواع محارف البدل عمومية، حيث يَعمَل مع أي نوع يُنفِّذ الواجهة Comparable، كما أن تابعه compareTo يَستقبِل النوع K أو أيًّا من أنواعه الأعلى supertype.

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

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

البحث عن القيم values

كما أوضحنا في نفس المقالة المشار إليها في الأعلى، يتناسب زمن تنفيذ التابع findNode مع ارتفاع الشجرة وليس مع عدد العقد الموجودة فيها؛ وذلك لأننا غير مضطرّين للبحث في كامل الشجرة، ولكن بالنسبة للتابع containsValue، فإننا سنضطرّ للبحث بالقيم وليس المفاتيح، ولأن خاصية BST لا تُطبَّق على القيم، فإننا سنضطرّ إلى البحث في كامل الشجرة.

يَستخدِم الحلُّ التالي التعاودَ recursion:

public boolean containsValue(Object target) {
    return containsValueHelper(root, target);
}

private boolean containsValueHelper(Node node, Object target) {
    if (node == null) {
        return false;
    }
    if (equals(target, node.value)) {
        return true;
    }
    if (containsValueHelper(node.left, target)) {
        return true;
    }
    if (containsValueHelper(node.right, target)) {
        return true;
    }
    return false;
}

يَستقبِل التابعُ containsValue المعاملَ target، ويُمرِّره مع معاملٍ إضافيٍّ يحتوي على عقدة الجذر إلى التابع containsValueHelper.

يَعمَل التابع containsValueHelper وفقًا لما يلي:

• تفحص تعليمة if الأولى الحالة الأساسية للتعاود: إذا كانت قيمة node مساويةً للقيمة الفارغة null، فإن التابع وصل إلى قاع الشجرة دون إيجاد القيمة المطلوبة target، ويعيد عندها القيمة false. انتبه، يعني ذلك أن القيمة target غير موجودةٍ في واحدٍ فقط من مسارات الشجرة لا في مسارات الشجرة كلّها، ولذا ما يزال من الممكن العثور عليها في مسارٍ آخر.
• تفحص تعليمة if الثانية ما إذا كان التابع قد وجد القيمة المطلوبة، وفي تلك الحالة، يعيد التابع القيمة true، أما إذا لم يجدها، فإنه يستمر في البحث.
• تَستدعِي الحالة الشرطية الثالثة التابعَ تعاوديًا لكي يبحث عن نفس القيمة، أي target، في الشجرة الفرعية اليسرى. إذا وجدها فيها، فإنه يعيد القيمة true مباشرةً دون أن يحاول البحث في الشجرة الفرعية اليمنى، أما إذا لم يجدها فيها، فإنه يستمر في البحث.
• تبحث الحالة الشرطية الرابعة عن القيمة المطلوبة في الشجرة الفرعية اليمنى. إذا وجدها فيها، فإنه يعيد القيمة true، أما إذا لم يجدها، فإنه يعيد القيمة false.

يمرّ التابع السابق عبر كل عقدةٍ من الشجرة، ولهذا، يَستغرِق زمنًا يتناسب مع عدد العقد.

تنفيذ التابع put

يُعدّ التابع put أعقد قليلاً من التابع get؛ لأن عليه أن يتعامل مع حالتين: الأولى عندما يكون المفتاح المُعطَى موجودًا في الشجرة بالفعل، وينبغي عندها أن يَستبدِله ويعيد القيمة القديمة، والثانية عندما لا يكون موجودًا، وعندها ينبغي أن يُنشِئ عقدةً جديدةً ثم يضعها في المكان الصحيح.

كنا قد وفّرنا الشيفرة المبدئية التالية لذلك التابع في المقالة المذكورة:

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);
}

وكان المطلوب هو إكمال متن التابع putHelper. انظر إلى شيفرته فيما يلي:

private V putHelper(Node node, K key, V value) {
    Comparable<? super K> k = (Comparable<? super K>) key;
    int cmp = k.compareTo(node.key);

    if (cmp < 0) {
        if (node.left == null) {
            node.left = new Node(key, value);
            size++;
            return null;
        } else {
            return putHelper(node.left, key, value);
        }
    }
    if (cmp > 0) {
        if (node.right == null) {
            node.right = new Node(key, value);
            size++;
            return null;
        } else {
            return putHelper(node.right, key, value);
        }
    }
    V oldValue = node.value;
    node.value = value;
    return oldValue;
}

يُضبَط المعاملُ الأوّلُ node مبدئيًا إلى عقدة الجذر root، وفي كل مرةٍ نَستدعِي فيها التابع تعاوديًّا، يشير المعامل إلى شجرةٍ فرعيّةٍ مختلفةٍ. مثل التابع get، اِستخدَمنا التابع compareTo لتحديد المسار الذي سنتبعه في الشجرة. إذا تحقّق الشرط cmp < 0، يكون المفتاح المطلوب إضافته أقلّ من node.key، وعندها يكون علينا فحص الشجرة الفرعية اليسرى. هنالك حالتان:

• إذا كانت الشجرةُ الفرعيّةُ فارغةً، فإن node.left تحتوي على null، وعندها نكون قد وصلنا إلى قاع الشجرة دون أن نعثر على المفتاح key. في تلك الحالة، نكون قد تأكّدنا من أن المفتاح key غير موجود في الشجرة، وعرفنا المكان الذي ينبغي أن نضيف المفتاح إليه، ولذلك، نُنشِئ عقدةً جديدةً، ونضيفها كعقدةٍ ابنةٍ يسرى للعقدة node.
• إن لم تكن الشجرة فارغةً، نَستدعِي التابع تعاوديًّا للبحث في الشجرة الفرعية اليسرى.

في المقابل، إذا تحقّق الشرط cmp > 0، يكون المفتاح المطلوب إضافته أكبر من node.key، وعندها يكون علينا فحص الشجرة الفرعية اليمنى، وسيكون علينا معالجة نفس الحالتين السابقتين. أخيرًا، إذا تحقّق الشرط cmp == 0، نكون قد عثرنا على المفتاح داخل الشجرة، وعندها، نستطيع أن نستبدله ونعيد القيمة القديمة.

كتبنا هذا التابع تعاوديًّا لكي نُسهِّل من قراءته، ولكن يُمكِن كتابته أيضًا بأسلوبٍ تكراريٍّ. يُمكِنك القيام بذلك كتمرين.

اجتياز في الترتيب In-order

كنا قد طلبنا منك كتابة التابع keySet لكي يعيد مجموعةً من النوع Set تحتوي على مفاتيح الشجرة مُرتَّبة تصاعديًّا. لا يعيد هذا التابع في التنفيذات الأخرى من الواجهة Map المفاتيح وفقًا لأيّ ترتيب، ولكن لأن هذا التنفيذَ يتمتع بالبساطة والكفاءة، فإنه يَسمَح لنا بترتيب المفاتيح، وعلينا أن نَستفيد من ذلك.

انظر إلى شيفرة التابع فيما يلي:

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

private void addInOrder(Node node, Set<K> set) {
    if (node == null) return;
    addInOrder(node.left, set);
    set.add(node.key);
    addInOrder(node.right, set);        
}

كما ترى فقد أنشأنا قيمةً من النوع LinkedHashSet في التابع keySet. يُنفِّذ ذلك النوع الواجهة Set ويحافظ على ترتيب العناصر (بخلاف معظم تنفيذات تلك الواجهة). نَستدعِي بعد ذلك التابع addInOrder لاجتياز الشجرة.

يشير المعامل الأول node مبدئيًّا إلى جذر الشجرة، ونَستخدِمه -كما يُفترَض أن تتوقَّع- لاجتياز الشجرة تعاوديًا. يجتاز التابع addInOrder الشجرة بأسلوب "في الترتيب" المعروف.

إذا كانت العقدة node فارغةً، يَعنِي ذلك أن الشجرةَ الفرعيةَ فارغةٌ، وعندها يعود التابع دون إضافة أيّ شيءٍ إلى المجموعة set، أما إذا لم تكن فارغةً، نقوم بما يلي:

1. نجتاز الشجرة الفرعية اليسرى بالترتيب.
2. نضيف node.key.
3. نجتاز الشجرة الفرعية اليمنى بالترتيب.

تذكّر أن خاصية BST تضمن أن تكون جميع العقد الموجودة في الشجرة الفرعية اليسرى أقلَّ من node.key وأن تكون جميع العقد الموجودة في الشجرة الفرعية اليمنى أكبرَ منه، أي أننا نضيف node.key إلى الترتيب الصحيح.

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

ولأن هذا التابع يمرّ عبر كل عقدةٍ ضمن الشجرة مثله مثل التابع containsValue، فإنه يَستغرِق زمنًا يتناسب مع n.

التوابع اللوغاريتمية

يَستغرِق التابعان get و put في الصنف MyTreeMap زمنًا يتناسب مع ارتفاع الشجرة h. أوضحنا في المقالة المشار إليها أنه إذا كانت الشجرة ممتلئةً أي كان كل مستوىً منها يحتوي على الحد الأقصى من عدد العقد المسموح به، فإن ارتفاع تلك الشجرة يكون متناسبًا مع log(n)‎.

نفترض الآن أن التابعين get و set يستغرقان زمنًا لوغاريتميًا، أي زمنًا يتناسب مع log(n)‎، مع أننا لا نَضمَن أن تكون الشجرة ممتلئةً دائماً. يعتمد شكل الشجرة في العموم على المفاتيح وعلى الترتيب الذي تُضاف به.

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

تُولِّد الشيفرةُ التاليةُ السلاسلَ النصيّة العشوائية:

Map<String, Integer> map = new MyTreeMap<String, Integer>();

for (int i=0; i<n; i++) {
    String uuid = UUID.randomUUID().toString();
    map.put(uuid, 0);
}

يقع تعريف الصنف UUID ضمن حزمة java.util، ويُمكِنه أن يُولِّد مُعرِّف هويةٍ فريدًا عموميًا universally unique identifier بأسلوبٍ عشوائي. تُعدّ تلك المُعرّفات ذاتَ فائدةٍ كبيرةٍ في مختلِف أنواع التطبيقات، ولكننا سنَستخدِمها في هذا المثال كطريقةٍ سهلةٍ لتوليد سلاسلَ نصيّةٍ عشوائيّةٍ.

شغّلنا الشيفرة التالية مع n=16384 وحسبنا زمن التنفيذ وارتفاع الشجرةِ النهائيّ، وحصلنا على الخرج التالي:

Time in milliseconds = 151
Final size of MyTreeMap = 16384
log base 2 of size of MyTreeMap = 14.0
Final height of MyTreeMap = 33

أضفنا أيضًا قيمة اللوغاريتم للأساس 2 إلى الخريطة لكي نرى طول الشجرة إذا كانت ممتلئة. تشير النتيجة إلى أن شجرةً ممتلئةً بارتفاعٍ يساوي 14 تحتوي على 16,384 عقدة.

في الواقع، ارتفاع شجرة السلاسل النصية العشوائية الفعلي هو 33، وهو أكبر من الحد الأدنى النظري ولكن ليس بشكل كبير. لكي نعثر على مفتاحٍ ضمن تجميعةٍ مكونةٍ من 16,384 عقدةً، سنضطرّ لإجراء 33 موازنةً، أي أسرع بـ 500 مرةً تقريبًا من البحث الخطي linear search.

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

في المقابل، لا تَعمَل أشجار البحث الثنائية بهذه الكفاءة دائمًا. لنرى ما قد يحدث عند إضافة المفاتيح بترتيبٍ تصاعديٍّ. يَستخدِم المثال التالي علاماتٍ زمنيةً -بوحدة النانو ثانية- كمفاتيح:

MyTreeMap<String, Integer> map = new MyTreeMap<String, Integer>();

for (int i=0; i<n; i++) {
    String timestamp = Long.toString(System.nanoTime());
    map.put(timestamp, 0);
}

يعيد System.nanoTime عددًا صحيحًا من النوع long يشير إلى الزمن المُنقضِي بوحدة النانو ثانية. نحصل على عددٍ أكبرَ قليلًا في كلّ مرةٍ نَستدعيه فيها. عندما نُحوِّل تلك العلامات الزمنية إلى سلاسلَ نصيّةٍ، فإنها تكون مُرتَّبة أبجديًّا.

لنرى ما نحصل عليه عند التشغيل:

Time in milliseconds = 1158
Final size of MyTreeMap = 16384
log base 2 of size of MyTreeMap = 14.0
Final height of MyTreeMap = 16384

يتجاوز زمن التشغيل في هذه الحالة سبعةَ أضعاف زمن التشغيل في الحالة السابقة. إذا كنت تتساءل عن السبب، فألق نظرةً على ارتفاع الشجرةِ النهائيّ 16384.

إذا أمعنت النظر في الطريقة التي يَعمَل بها التابع put، فقد تفهم ما يحدث: ففي كل مرةٍ نضيف فيها مفتاحًا جديدًا، فإنه يكون أكبر من جميع المفاتيح الموجودة في الشجرة، وبالتالي، نضطرّ دائمًا لاختيار الشجرة الفرعية اليمنى، ونضيف دائمًا العقدة الجديدة كعقدة ابن يمنى للعقدة الواقعة على أقصى اليمين. نحصل بذلك على شجرة غير متزنة unbalanced تحتوي على عقدٍ أبناء يمنى فقط.

يتناسب ارتفاع تلك الشجرة مع n وليس log(n)‎، ولذلك يصبح أداء التابعين get و set خطيًا لا لوغاريتميًا.

تَعرِض الصورة السابقة مثالًا عن شجرتين إحداهما متزنة والأخرى غير متزنة. يُمكِننا أن نرى أن ارتفاع الشجرة المتزنة يساوي 4 وعدد العقد الكلية يساوي 2⁴−1 أي 15. تحتوي الشجرة غير المتزنة على نفس عدد العقد، ولكن ارتفاعها يساوي 15.

الأشجار المتزنة ذاتيا Self-balancing trees

هناك حلّان محتملان لتلك المشكلة:

• يُمكِننا أن نتجنّب إضافة المفاتيح إلى الخريطة بالترتيب، ولكن هذا الحل ليس ممكنًا دائمًا.
• يُمكِننا أن نُنشِئ شجرةً قادرةً على التعامل مع المفاتيح المرتّبة تعاملًا أفضل.

يبدو الحل الثاني أفضل، وتتوفّر طرائقُ عديدةٌ لتنفيذه. يُمكِننا مثلًا أن نُعدّل التابع put لكي نجعله يفحص ما إذا كانت الشجرة قد أصبحت غير متزنة، وعندها، يعيد ترتيب العقد. يُطلَق على الأشجار التي تتميز بتلك المقدرة اسم "الأشجار المتزنة ذاتيًا"، ومن أشهرها شجرة AVL (اختصار Adelson-Velskii Tree حيث إن Adelson و Velskii هما مبتكرا هذه الشجرة)، وشجرة red-black التي يَستخدِمها صنف الجافا TreeMap.

إذا استخدمنا الصنف TreeMap بدلًا من الصنف MyTreeMap في الشيفرة السابقة، سيصبح زمن تشغيل مثالِ السلاسل النصية ومثالِ العلامات الزمنية هو نفسه، بل في الحقيقة، سيكون مثال العلامات الزمنية أسرع على الرغم من أن المفاتيح مُرتَّبة؛ لأنه يَستغرِق وقتًا أقل لحساب شيفرة التعمية hash.

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

يُمكِنك قراءة المزيد عن الأشجار المتزنة ذاتيًّا.

تمرين إضافي

لم نُنفِّذ التابع remove في ذاك التمرين، ولكن يُمكِنك أن تُجرِّب كتابته الآن. إذا حذفت عقدةً من وسط الشجرة، ستضطرّ إلى إعادة ترتيب العقد المتبقية لكي تحافظ على خاصية BST. 

تُعدّ عمليتا حذف عقدةٍ وإعادة الشجرة إلى الاتزان عمليتين متشابهتين، لذا إذا أتممت هذا التمرين، ستفهم طريقة عمل الأشجار المتزنة ذاتيًا فهماً أعمق.

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

اقرأ أيضًا

• تحسين أداء الخرائط المنفذة باستخدام التعمية HashMap في جافا
• تحليل زمن تشغيل الخرائط المنفذة باستخدام مصفوفة في جافا
• استخدام خريطة ومجموعة لبناء مفهرس Indexer