شجرة ثنائية مفهرسة

لقد واجهت النوع التالي من المشاكل. من الضروري تنفيذ حاوية تخزين البيانات التي توفر الوظائف التالية:

• أدخل عنصرا جديدا
• إزالة العنصر عن طريق الرقم التسلسلي
• الحصول على العنصر بالرقم الترتيبي
• يتم تخزين البيانات في شكل مرتبة

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

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

ستحتوي المقالة على صور ونظرية أكثر من التعليمات البرمجية. يمكن الاطلاع على الكود على الرابط أدناه.

الوزن

ولتحقيق ذلك خضعت الشجرة لتعديل بسيط وتم إضافة معلومات إضافية عنها وزن العقدة. وزن العقدة هو عدد أحفاد هذه العقدة + 1 (وزن عنصر واحد).

وظيفة الحصول على وزن العقدة:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

وزن الورقة يساوي في المقابل 0.

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

عندما تكون شجرتنا فارغة، يكون وزنها 0. فلنضف عنصرًا جذريًا إليها:

يصبح وزن الشجرة 1، ويصبح وزن العنصر الجذري 1. وزن العنصر الجذري هو وزن الشجرة.

دعونا نضيف بعض العناصر الأخرى:

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

مؤشرات

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

العقدة الأولى لديها فهرس 0والآن هناك حالتان محتملتان. في الأول، سيتغير مؤشر العنصر الجذر، وفي الثانية لن يتغير.

عند الجذر، تزن الشجرة الفرعية اليسرى 1.

الحالة الثانية:

لم يتغير مؤشر الجذر لأن وزن الشجرة الفرعية اليسرى ظل 0.

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

على سبيل المثال، كيفية حساب فهرس العنصر الذي يحتوي على المفتاح 8 (الفرع الأيمن للجذر). هذا هو "فهرس الجذر" + "وزن الشجرة الفرعية اليسرى للعقدة ذات المفتاح 8" + "1" == 3 + 2 + 1 == 6
فهرس العنصر الذي يحتوي على المفتاح 6 سيكون "فهرس الجذر" + 1 == 3 + 1 == 4

وفقًا لذلك، يستغرق الحصول على عنصر وحذفه حسب الفهرس وقتًا O (تسجيل ن)لأنه لكي نحصل على العنصر المطلوب يجب أن نجده أولاً (ننزل من الجذر إلى هذا العنصر).

عمق

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

كود تحويل الوزن الى عمق.

/*
 * Возвращает первое число в степени 2, которое больше или ровно x
 */
uint64_t bntree::cpl2(uint64_t x) {
    x = x - 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    x = x | (x >> 32);

    return x + 1;
}

/*
 * Двоичный логарифм от числа
 */
long bntree::ilog2(long d) {
    int result;
    std::frexp(d, &result);
    return result - 1;
}

/*
 * Вес к глубине
 */
uint64_t bntree::weight_to_depth(node_t *p) {
    if (p == NULL) {
        return 0;
    }

    if (p->weight == 1) {
        return 1;
    } else if (p->weight == 2) {
        return 2;
    }

    return this->ilog2(this->cpl2(p->weight));
}

نتائج

• يحدث إدخال عنصر جديد في O (تسجيل ن)
• يحدث حذف عنصر بالرقم التسلسلي في O (تسجيل ن)
• يحدث الحصول على عنصر بالرقم التسلسلي في O (تسجيل ن)

سرعة O (تسجيل ن) نحن ندفع مقابل تخزين جميع البيانات في شكل مرتبة.

لا أعرف أين قد يكون مثل هذا الهيكل مفيدًا. مجرد لغز لفهم كيفية عمل الأشجار مرة أخرى. شكرًا لكم على اهتمامكم.

مراجع

• كود مصدر الشجرة

يحتوي المشروع على بيانات اختبارية للتحقق من سرعة التشغيل. الشجرة تمتلئ 1000000 عناصر. ويوجد حذف وإدراج واسترجاع للعناصر بشكل متسلسل 1000000 مرة واحدة. إنه 3000000 عمليات. وكانت النتيجة جيدة جدًا ~ 8 ثوانٍ.

المصدر: www.habr.com