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

حصلت على المشكلة التالية. من الضروري تطبيق حاوية تخزين البيانات التي توفر الوظائف التالية:

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

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

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 . إذا كانت هناك عقدة بمثل هذا المفتاح موجودة بالفعل ، فقم بإعادة كتابة القيمة والعودة إلى الجذر ، مع إلغاء التغييرات في أوزان جميع العقد التي مررنا بها.
إذا تم إزالة العقدة ، فنحن ننزول ونخفض الأوزان في العقد.

مؤشرات

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

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

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

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

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

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

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

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

عمق

بناءً على الوزن ، يمكنك أيضًا حساب عمق الشجرة. ضروري لتحقيق التوازن.
للقيام بذلك ، يجب تقريب وزن العقدة الحالية إلى الرقم الأول في الدرجة 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 (سجل n)
• حذف العنصر برقم التسلسل يحدث في O (سجل ن)
• الحصول على عنصر برقمه التسلسلي يحدث في O (سجل ن)

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

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

مراجع

• رمز مصدر الشجرة

يحتوي المشروع على بيانات اختبار للتحقق من سرعة العمل. تمتلئ الشجرة مع 1،000،000 العناصر. وهناك حذف متسلسل وإدراج واستلام العناصر 1،000،000 مرة. هذا هو 3،000،000 العمليات. وكانت النتيجة جيدة جدا ~ 8 ثوان.