TechCodeview

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

ما هي الشجرة الحمراء السوداء؟

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

ملكيات

فيما يلي الخصائص المرتبطة بالشجرة ذات اللون الأحمر والأسود:

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

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

دعونا نفهم هذه الخاصية من خلال مثال.

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

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

ارتفاع شجرة حمراء سوداء

اعتبر h ارتفاع الشجرة التي تحتوي على n عقد. ما هي أصغر قيمة لـ n ؟. قيمة n هي الأصغر عندما تكون جميع العقد سوداء. إذا كانت الشجرة تحتوي على جميع العقد السوداء، فستكون الشجرة شجرة ثنائية كاملة. إذا كان ارتفاع الشجرة الثنائية الكاملة هو h، فإن عدد العقد في الشجرة هو:

البرنامج التعليمي السيلينيوم

n = 2h -1

ما هي أكبر قيمة لـ n؟

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

n = 2*2h-1

ما هي شجرة AVL؟

ان شجرة AVL هي شجرة بحث ثنائية ذاتية التوازن إذا لاحظنا الحالة أدناه، وهي شجرة بحث ثنائية وشجرة متوازنة.

في الشجرة أعلاه، أسوأ تعقيد زمني للبحث عن عنصر هو O(h)، أي ارتفاع الشجرة. في الحالة أعلاه، عدد المقارنات التي تم إجراؤها للبحث عن 17 عنصر هو 4، وارتفاع الشجرة هو 4 أيضًا.

إذا نظرنا إلى الشجرة الثنائية المنحرفة، كما هو موضح أدناه:

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

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

يمكن أن تكون قيمة عامل التوازن إما 1 أو 0 أو -1. إذا كانت كل عقدة في الشجرة الثنائية لها قيمة إما 1 أو 0 أو -1، فيُقال أن تلك الشجرة متوازنة شجرة ثنائية أو شجرة AVL.

تُعرف الشجرة بأنها شجرة متوازنة تمامًا إذا كان عامل التوازن لكل عقدة هو 0. تعتبر شجرة AVL شجرة متوازنة تقريبًا لأن كل عقدة في الشجرة لها قيمة عامل التوازن إما 1 أو 0 أو -1.

الاختلافات بين الشجرة الحمراء السوداء وشجرة AVL.

فيما يلي الاختلافات بين الشجرة ذات اللون الأحمر والأسود وشجرة AVL:

شجرة البحث الثنائية

الشجرة الحمراء-السوداء هي شجرة بحث ثنائية، وشجرة AVL هي أيضًا شجرة بحث ثنائية.

قواعد

يتم تطبيق القواعد التالية في الشجرة ذات اللون الأحمر والأسود:

1. العقدة في الشجرة ذات اللون الأحمر والأسود تكون إما حمراء أو سوداء اللون.
2. يجب أن يكون لون العقدة الجذرية أسود.
3. لا ينبغي أن تكون العقد المجاورة حمراء. بمعنى آخر، يمكننا القول أن العقدة الحمراء لا يمكن أن يكون لها أطفال حمر، لكن العقدة السوداء يمكن أن يكون لها أطفال سود.
4. يجب أن يكون هناك نفس العدد من العقد السوداء في كل مسار؛ إذن، يمكن اعتبار الشجرة فقط شجرة ذات لون أحمر وأسود.
5. العقد الخارجية هي العقد الصفرية، والتي تكون دائمًا سوداء اللون.

قاعدة شجرة AVL:

يجب أن يكون لكل عقدة عامل التوازن إما -1 أو 0 أو 1.

مثال

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

في الشكل أعلاه، نحتاج إلى التحقق مما إذا كانت الشجرة هي شجرة AVL أم لا. نظرًا لأن كل عقدة لها قيمة عامل التوازن إما -1 أو 0 أو 1، فهي شجرة AVL.

فكيف يمكن اعتبار الشجرة شجرة متوازنة أم لا؟

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

في حالة شجرة AVL، إذا كان عامل التوازن هو -1، 0، أو 1، يقال إن الشجرة أعلاه هي شجرة AVL.

الأدوات المستخدمة في التوازن

إذا كانت الشجرة غير متوازنة، فسيتم استخدام أداتين لموازنة الشجرة في شجرة حمراء وسوداء:

إعادة تلوين دوران

إذا كانت الشجرة غير متوازنة، فسيتم استخدام أداة واحدة لموازنة الشجرة في شجرة AVL:

دوران

فعالة لأي عملية

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

في حالة شجرة AVL، تكون عملية البحث فعالة لأنها تتطلب أداة واحدة فقط لموازنة الشجرة.

تعقيد الوقت

في حالة الشجرة ذات اللون الأحمر والأسود، يكون التعقيد الزمني لجميع العمليات، أي الإدراج والحذف والبحث، هو O(logn).

في حالة شجرة AVL، يكون التعقيد الزمني لجميع العمليات، أي الإدراج والحذف والبحث، هو O(logn).

دعونا نفهم الاختلافات في النموذج الجدولي.