شجرة باللون الأحمر والأسود: أشجار البحث الثنائية المتوازنة ذاتيًا موضحة بأمثلة

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

Red-Black Tree هو نوع من شجرة البحث الثنائية ذاتية التوازن (BST). في شجرة الأحمر والأسود ، تتبع كل عقدة القواعد التالية:

  1. كل عقدة لها طفلان ملونان إما باللون الأحمر أو الأسود.
  2. كل عقدة أوراق شجرة سوداء دائمًا.
  3. كل عقدة حمراء لها أطفالها بلون أسود.
  4. لا توجد عقدتان متجاورتان أحمرتان (لا يمكن أن تحتوي العقدة الحمراء على أحد الوالدين الأحمر أو الطفل الأحمر).
  5. يحتوي كل مسار من الجذر إلى عقدة طرفية على نفس عدد العقد السوداء (تسمى "الارتفاع الأسود").

الإدراج في أشجار الأحمر والأسود

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

شجرة حمراء-سوداء ذات ميول يسارية

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

خصائص الأشجار المائلة اليسرى ذات اللون الأحمر والأسود

تتميز جميع خوارزميات الشجرة ذات اللون الأحمر والأسود التي تم اقتراحها بوقت بحث في أسوأ حالة يحده مضاعف ثابت صغير لسجل N في شجرة مفاتيح N ، والسلوك الملاحظ عمليًا هو نفس المضاعف أسرع الحد الأسوأ ، بالقرب من العقد الأمثل لوغاريتم N التي تم فحصها والتي يمكن ملاحظتها في شجرة متوازنة تمامًا.

على وجه التحديد ، في شجرة ذات اتجاهين يسارًا باللون الأحمر والأسود 2-3 مبنية من مفاتيح عشوائية N: -> بحث عشوائي ناجح يفحص log2 N- 0.5 عقدة. -> متوسط ​​ارتفاع الشجرة حوالي2 log2 N