خوارزمية تكرارية لشجرة اللون الأسود الأحمر

Question

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

ملاحظة: يستخدم Goletas.Collection خوارزمية تكرارية لشجرة AVL التي تعتبر فعالة للغاية لعدد كبير من البيانات ، أريد شيئًا مشابهًا لشجرة اللون الأسود الأحمر أيضًا.

Answer 1

شكرا للجميع على تعليقاتك القيمة. لقد وجدت واحدة فقط ولكن في VB6 و C. أعتقد أنه يكفي لفهم الفكرة. ها هي الروابط

1. مقالة - سلعة
2. مصدر C.
3. مصدر VB

آمل أن يجدها شخص ما مفيدًا. قون

Answer 2

الخوارزميات القائمة على الأشجار هي بطبيعتها العودية.

طبعا انت استطاع أعد كتابتهم ليكونوا تكراريين ولكن هذا سيكون تمرينًا في عدم جدوى. هنا لماذا:

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

- التمسك بالكروية ، لا بأس.

Answer 3

هناك نسخة في مقدمة إلى الخوارزميات بقلم توماس هورمين ، تشارلز إي ليسرسون ، رونالد ليفست ، كليفورد شتاين.

رمز الزائفة متاح على الإنترنت على كتب Google (صفحة 270).

كما هو موضح في التعليقات ، نهج نسخ البيانات إلى العقدة z بدلا من الاستبدال z بواسطة y في السطر 14/15 ليس الأمثل ، خاصة إذا كان لديك مؤشرات للعقد في مكان آخر. لذلك يمكن أن يكون السطر 13-16 بدلاً من ذلك:

do_fixup = y.color == BLACK

if y is not z:
    replace_parent(tree, y, z)
    y.left = z.left
    y.left.parent = y
    y.right = z.right
    y.right.parent = y
    y.color = z.color

if do_fixup:
    ...

أين replace_parent يتم تعريفه على أنه (يمكن استخدام هذا للخط 7-12 أيضًا):

def replace_parent(tree, a, b):
    a.parent = b.parent
    if not b.parent:
        tree.root = a
    else:
        if b is b.parent.left:
            b.parent.left = a
        else:
            b.parent.right = a