العثور على خوارزمية في rbtree في O (logn)

Question

أحتاج إلى العثور على بنية بيانات يمكنني القيام بها مع الإجراءات التالية:

• بناء (S، K) - O (NLGON)
• البحث (S، K) - O (logn)
• إدراج (S، K) - O (logn)
• حذف (S، K) - O (LOGN)
• تنقص-تصل إلى (S، K، D) - O (logn) - يجب أن تطرح هذه الطريقة (D> 0) كل عقدة <= k

كان Choise الواضح الأول Redblacktree.

ومع ذلك، لا أستطيع الوصول إلى حل بشأن الانخفاض - تصل إلى O (LOGN). ما يحدث إذا كان K أكبر، ثم مفتاح الحد الأقصى في الشجرة - هذه الحالة أنا فلدي تحديث الشجرة بأكملها.

هل يمكن لشخص ما أن يقترح خلاف ذلك؟ ربما بعض النصائح؟

Answer 1

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

لكى يفعل Decrease-Upto, ، يمكنك فقط تغيير Deltas of O (سجل N) العقد على مسار واحد من الجذر.

ليس لديك لتغيير هيكل الشجرة بعد هذه العملية، لأنها لا تغير طلب المفاتيح.