أفضل BST ذاتي التوازن للإدخال السريع لعدد كبير من العقد

Question

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

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

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

Answer 1

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

Answer 2

لماذا استخدام أ BST على الاطلاق؟من خلال وصفك، سيعمل القاموس أيضًا، إن لم يكن أفضل.

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

Answer 3

وهما التوازن الذاتي BSTأكثر ما أعرفه هو اللون الأحمر والأسود و AVL, ، لذلك لا أستطيع أن أقول على وجه اليقين ما إذا كانت هناك حلول أخرى أفضل، ولكن على ما أذكر، يتميز اللون الأحمر والأسود بإدراج أسرع واسترجاع أبطأ مقارنة بـ AVL.

لذا، إذا كان الإدراج يمثل أولوية أعلى من الاسترجاع، فقد يكون اللون الأحمر والأسود حلاً أفضل.

Answer 4

[تحتوي جداول التجزئة] على إدراج وبحث O(1).

أعتقد أن هذا خطأ.

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

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

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

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