معالجة كل ورقة تحت عقدة في شجرة بكفاءة

Question

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

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

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

الآن أنا تكرار فوق جميع المجلدات> المجلدات الفرعية> إلخ> الأطفال للتحقق من إدخال التاريخ وإعادة التوحيد. هذا هو الحصول على بطيئة جدا الآن لذلك أحتاج إلى نهج جديد.

لقد جئت مع خيارين ولكنهم يريدون معرفة ما إذا كان هناك نهج أفضل، أو أي واحد من هذه الأفضل.

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

الخيار 2: لديك وظيفة مؤقت تشغيل وتحديث خصائص "المستندات" و "UnopenedDoCumentCUNT" لكل مجلد في النظام، ستكون الكثير من دورات وحدة المعالجة المركزية ويبدو مضيعة.

الخيار 3 : فقط فكر في هذا - ربما تتكرر كل وثيقة ورؤية إذا كانت المستند طفلا مباشرا أو بعيد للعقدة المستهدفة قبل التقييم سيكون أفضل من التكرار عبر العودية. أشعر أن هذا سيكون أفضل لعقد العقد المتزايد في الشجرة، لكن تكرار كل طفل لعقدة منخفضة المستوى سيكون سخيفا. هممم ...

أنا إغراء لتنفيذ الخيار 1 .. ما هي الخيارات الأخرى هناك؟

Answer 1

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

وبالمثل، كما يمكنك تحديث العقد، فإنك تكرر إليهم، ثم احترف من القروض وتحديث الوالدين.

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

ملاحظة: إذا كان أعلاه لا معنى له، اقرأ Knuth Vol.1 .