ثلاثي مع مفاتيح ضمنية

Question

هناك بنية بيانات تسمى Treap: هذه شجرة بحث ثنائية عشوائية ، وهي أيضًا كومة على ما يسمى بأولويات ما يسمى بشكل عشوائي.

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

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

هل يمكن لأي شخص أن يوجهني إلى المقال حول هذا الهيكل أو يخبرني اسمه الأصلي؟ شكرًا لك.

ملاحظة: إذا لم تكن لغتي الإنجليزية مفهومة بما فيه الكفاية.

UPD: بعض التفسير الإضافي حول الهيكل الذي أبحث عنه.

النظر في ثلاثية معتادة مع الأولويات والمفاتيح التي تم اختيارها عشوائيا ، والتي هي بيانات المستخدم الفعلية المخزنة في الشجرة. ثم دعونا نتخيل أن لدينا بعض معلومات المستخدم الأخرى المخزنة في كل عقدة ، والمفاتيح ليست سوى مفاتيح البحث. الخطوة التالية هي حساب والحفاظ على حجم الشجرة الفرعية في كل عقدة: يتعين علينا تحديث هذه المعلمة بعد كل دمج/تقسيم/إضافة/إزالتها ، ولكنها تتيح لنا العثور ، على سبيل المثال ، عنصر KTH من الشجرة في O (log n) زمن.

عندما يكون لدينا أحجام شجرة فرعية في كل عقدة ، يمكننا التخلص من المفاتيح والتخيل أن Treap يمثل مجموعة من بيانات المستخدم في اجتياز inorder. يمكن حساب فهرس الصفيف لكل عنصر بسهولة من أحجام الشجرة الفرعية. الآن يمكننا إضافة/إزالة عنصر في منتصف الصفيف أو تقسيم هذا الصفيف - كل ذلك في وقت O (log n).

يمكننا أيضًا إجراء عملية "متعددة" - على سبيل المثال ، إضافة قيمة ثابتة إلى جميع عناصر "Array". لتنفيذ هذا ، يتعين علينا أن نؤخر هذه العملية ، وإضافة معلمة في كل عقدة تمثل ثابتًا تأخيرًا يجب أن يكون "لاحقًا" إضافة إلى جميع عناصر هذه العقدة الفرعية ، و "دفع" التغييرات لأسفل إلى أسفل. من الضروري. إضافة ثابتة إلى المستعار الفرعي أو الرسم (وضع العلامات) يمكن تأخير المساعد الفرعي بهذه الطريقة ، حيث عكس العكس الفرعي (هنا المعلومات المتأخرة في العقدة في BIT "يجب عكس" الفرعية ") ، وهكذا.

UPD2: هنا رمز مقتطف - جزء من كمية صغيرة من المعلومات التي وجدتها. لا تلاحظ السيريليك :) الكلمات "с н нввны к к" يعني في الترجمة المباشرة "مع مفتاح ضمني".

Answer 1

يمكنك العثور على بنية البيانات هذه في الورقة بواسطة Kaplan و Verbin عند فرز التباديل الموقعة بواسطة الانعكاسات (صفحة 7 ، القسم 3.1): http://www.math.jussieu.fr/~fouquet/enseignement/projets/kaplan.pdf.

Answer 2

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

مع Treaps ، يمكنك القيام بذلك باستخدام أولويات عشوائية وموازنة.

مع الأشجار الثنائية العشوائية ، يتم تضمين العشوائية فقط أثناء البناء: أي عندما تقوم بإدراج عقدة في شجرة T ، فإن لديها احتمال 1/(الحجم (T) + 1) في الجذر ، حيث الحجم (T) هو عدد العقد من t ؛ وبالطبع إذا لم يتم إدخال العقدة في الجذر ، فستتابع بشكل متكرر حتى يتم إضافتها. (انظر المقالات My C. Martinez للحصول على دراسة مفصلة لهذه الأشجار.)

يتصرف بنية البيانات هذه تمامًا مثل Treap ، ولكنه يستخدم آلية مختلفة لا تتطلب مفاتيح.

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

Answer 3

ربما كنت تبحث عن حبل (شكل معقد من السلسلة) تم تعديله لاحتياجاتك للعمليات المتأخرة. الشيء المثير للاهتمام هو أن هناك سؤال مفتوح بخصوص الحبال هنا الآن.

Answer 4

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

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