عند التحويل إلى شجرة ذات لون أحمر وأسود، هل هناك أي سبب لاختيار شكل واحد على الآخر؟

Question

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

تقوم إحدى الطرق بالتحويل من قائمة مرتبطة مزدوجة إلى شجرة ثنائية بسيطة ومتوازنة تمامًا O(n) الوقت (مع العلم أن عدد العناصر معروف مسبقًا).تُعرف الخوارزمية باسم "الطي" - وهي النصف الثاني من خوارزمية إعادة توازن الشجرة الثنائية التي تم نشرها ذات مرة في مجلة Dr.دوبس.الخطوات هي في الأساس ...

• نظرًا لحجم الشجرة، حدد حجم الشجرتين الفرعيتين اليمنى واليسرى

• التكرار للشجرة الفرعية اليسرى

• قم بإخراج عقدة من القائمة لاستخدامها كجذر

• تكرار للشجرة الفرعية الصحيحة

• ربط الأشجار الفرعية بالجذر

لدي أيضًا طريقة مماثلة لإنشاء شجرة حمراء سوداء.المبدأ هو نفسه، لكن التكرار يتتبع ارتفاع العقدة - يتم إنشاء العقد ذات الارتفاع الصفري باللون الأحمر، وجميع العقد الأخرى باللون الأسود.يعتمد حساب ارتفاع البداية على أعلى بتة محددة في حجم الشجرة، ويتم التلاعب بها بحيث تكون متوازنة تمامًا (2^n)-1 تحتوي الشجرة ذات الحجم الكبير على عقد سوداء فقط (ينخفض ​​التكرار إلى الارتفاع واحد فقط).

النقطة المهمة هنا هي أن لدي عقدًا حمراء فقط على مستوى الورقة، وأن نصف العقد كحد أقصى على وجه التحديد تكون حمراء.

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

السؤال هو - هل هناك أي سبب عملي لاختيار شكل شجرة أحمر-أسود صالح على شكل آخر؟

هذا مجرد فضول - أعلم أنه ليس لدي أي سبب عملي - ولكن هل يعرف أحد تطبيقًا متخصصًا يكون فيه هذا الاختيار مهمًا؟

Answer 1

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

لذلك، لتقليل تكلفة التعديلات، أعط كل عقدة سوداء طفلًا أحمر واحدًا.

---

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

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

الرقم الثنائي الزائد هو رقم يمثل فيه الرقم 2^أنا, ، تمامًا كما هو الحال في الرقم الثنائي القياسي، لكن الرقم i يمكن أن يكون 0، 1، أو 2.يطلق عليها اسم زائدة عن الحاجة لأن هناك طرقًا متعددة لكتابة رقم معين.4_ديسمبر يمكن كتابتها 100 أو 20 أو 12.

لإضافة رقم إلى رقم ثنائي متكرر، يمكنك زيادة الرقم الأقل أهمية؛إذا كان 3، فاضبطه على 1 وقم بزيادة الرقم التالي الأقل أهمية، وهكذا.تتوقف الخوارزمية عندما تواجه 0 أو 1.

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

لتقييد التكلفة المطفأة لزيادة رقم ثنائي زائد عن الحاجة، استخدم طريقة الفيزيائيين وقم بتعيين احتمال 1 لكل رقمين.تؤدي زيادة xall التي تلامس k إلى إطلاق إمكانات k-1، مما يمنحها تكلفة مطفأة قدرها O(1).

يشبه هذا التحليل التكلفة المطفأة لزيادة الرقم الثنائي القياسي، ولكن الرقم الثنائي القياسي لا يمكنه دعم الزيادة والنقصان في O(1) الوقت المطفأ:اعتبر 2^ك - 1.هو ك 1 أرقام.زيادة التكاليف Θ(ك).إذا أعقب ذلك إنقاص، فإن الزوج يكلف Θ(k) ويعيد الرقم إلى حالته القديمة.

يعد الثنائي الزائد خاصًا حيث يقوم رقم واحد بإيقاف العمليات المتتالية لكل من الزيادة والنقصان.تعتبر 2-4 أشجار خاصة حيث أن العقد الثلاثة توقف العمليات المتتالية لكل من الإدراج والحذف.

في الأشجار ذات اللون الأحمر والأسود، تكون العقدة ذات الطفل الأحمر مجرد تمثيل لثلاثة عقد في شجرة مكونة من 2-4.هذه العقد مميزة وقوية ضد عمليات الإدراج أو الحذف في أشجارها الفرعية، لذا يجب عليك تفضيلها عند إنشاء أشجار ذات لون أحمر وأسود والتي ستشهد الكثير من التحديثات.

إذا كنت تعلم أنك لن ترى سوى الإدخالات، ففضل العقد التي تحتوي على طفلين أسودين.إذا كنت تعلم أنك لن ترى سوى عمليات الحذف، ففضل العقد التي تحتوي على طفلين باللون الأحمر.

Answer 2

الجواب القصير هو: هذا يعتمد.

في الأساس، أي شجرة صالحة ستكون كافية.ومع ذلك، من حيث التحليل المطفأ - من المحتمل جدًا أنك سترغب في اختيار الشجرة الصحيحة التي ستمنحك على المدى الطويل السلوك الأمثل.

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

يعتمد ذلك، لأن هذا عادةً ما يكون خاصًا بالتطبيق.