ما هو تطبيق شجرة C++ الجيد والمستقر؟

Question

أتساءل عما إذا كان يمكن لأي شخص أن يوصي بتنفيذ شجرة C ++ جيدة ، ونأمل أن يكون STL متوافقًا إذا كان ذلك ممكنًا.

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

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

Answer 1

وأنا لا أعرف عن الاحتياجات الخاصة بك، ولكن لن تكون أفضل حالا مع الرسم البياني (تطبيقات على سبيل المثال في <لأ href = "http://www.boost.org/doc/libs/release/libs /graph/doc/index.html "يختلط =" noreferrer "> زيادة الرسم البياني ) إذا كنت مهتما في الغالب في هيكل وليس ذلك بكثير في فوائد شجرة معينة مثل سرعة من خلال موازنة؟ يمكنك 'محاكاة' شجرة من خلال الرسم البياني، وربما أنه سوف يكون (نظريا) أقرب إلى ما كنت تبحث عنه.

Answer 2

ونلقي نظرة على هذا .

والمكتبة tree.hh لC ++ توفر فئة حاوية مثل STL لأشجار ن آرى، قالب على البيانات المخزنة في العقد. يتم توفير أنواع مختلفة من التكرارات (ما بعد النظام، قبل النظام، وغيرها). حيثما أمكن ذلك أساليب الوصول متوافقة مع المحكمة الخاصة بلبنان أو خوارزميات البديلة المتاحة.

وHTH

Answer 3

وانا ذاهب الى أقترح استخدام الأمراض المنقولة جنسيا :: خريطة بدلا من شجرة.

وخصائص تعقيد شجرة هي:

وإدراج: O (قانون الجنسية (ن))
إزالة: O (قانون الجنسية (ن))
البحث: O (قانون الجنسية (ن))

وهذه هي نفس الخصائص الضمانات الأمراض المنقولة جنسيا :: الخريطة.
وبالتالي نتيجة لذلك معظم تطبيقات من الأمراض المنقولة جنسيا :: خريطة استخدام شجرة (الأحمر الأسود شجرة) تحت الأغطية (على الرغم من الناحية الفنية هذا غير مطلوب).

Answer 4

والناس طيب، ولقد وجدت مكتبة شجرة أخرى. stlplus.ntree . ولكن لم يحاكم بعد.

Answer 5

إذا لم يكن لديك (مفتاح، قيمة) زوجا، ولكن ببساطة مفاتيح، واستخدام الأمراض المنقولة جنسيا :: تعيينها. يستخدم نفس الحمراء الأسود شجرة كما الأمراض المنقولة جنسيا :: الخريطة.

Answer 6

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

تسمح الأشجار الثنائية المتوازنة، مثل المتجه، بإدارة بعض ترتيب العناصر دون الحاجة إلى مفتاح (مثل إدراج عناصر في أي مكان في المتجه)، ولكن:

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

بشكل اختياري، يمكن دعم الوصول عن طريق الفهرس كما هو الحال في المتجه (بتكلفة size_t واحدة لكل عنصر)، مع تعقيد O(log(n)).إذا تم استخدامها، ستكون التكرارات عشوائية.

يمكن فرض الطلب بشكل اختياري من خلال بعض وظائف المقارنة، ولكن استمرار التكرارات يسمح باستخدام نظام مقارنة غير قابل للتكرار (على سبيل المثال:تتغير ممرات السيارات بشكل تعسفي أثناء الازدحام المروري).

في الممارسة العملية، تحتوي الشجرة الثنائية المتوازنة على واجهة متجهة، وقائمة، وقائمة مرتبطة مزدوجة، وخريطة، وخرائط متعددة، وdeque، وqueue، وpriority_queue...مع تحقيق التعقيد النظري الأمثل لـ O(log(n)) لجميع عمليات العنصر الفردي.

<sarcastic> ربما يكون هذا هو سبب عدم اقتراح c++ stl له </sarcastic>

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

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