أضف إلى sortedset وتعقيدها

Question

ينص MSDN على ما يلي طريقة sortedset (t) .Add :

إذا كان العد أقل من قدرة الصفيف الداخلي ، فإن هذه الطريقة هي عملية O (1).

هل يمكن لأحد أن يشرح "كيف هكذا"؟ أعني عند إضافة قيمة جديدة ، نحتاج إلى إيجاد مكان صحيح لإضافة قيمة (مقارنة مع قيم أخرى) ، ويبدو التنفيذ الداخلي وكأنه "شجرة أسود حمراء" مع تعقيد الإدراج O (log n).

Answer 1

التعليق ببساطة خاطئ. نعم ، إنها شجرة أسود حمراء ، o (سجل (n)) للإدراج. إلقاء نظرة مع العاكس يحمل هذا الأمر ، تحتوي طريقة Addifnotpresent () الخاصة على حلقة Thane () للعثور على نقطة الإدراج ، باستخدام عبور العقدة الحمراء العادية.

هذا علة المستند بالفعل تم تقديمه من قبل معرفة من.