دوران الشجرة

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

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

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

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

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

لنفترض المصطلحات التالية: الجذر (Root) للعقدة الأبوية للأشجار الفرعية المراد تدويرها، والمحور (Pivot) للعقدة التي ستصبح العقدة الأبوية الجديدة، وRS لجانب التدوير، و OS للجانب المقابل. بالنسبة للجذر Q في الرسم التوضيحي أعلاه، RS هو C و OS هو P. باستخدام هذه المصطلحات، تكون الشفرة الزائفة للتدوير كما يلي:

let Pivot = Root.OS Root.OS = Pivot.RS Pivot.RS = الجذر الجذر = محور

هذه عملية زمنية ثابتة.

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

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

الشجرة اليسرى: ((A, P, B), Q, C) الشجرة اليمنى: (A, P, (B, Q, C)) 

حساب أحدهما من الآخر أمر بسيط للغاية. فيما يلي مثال على كود بايثون يقوم بهذا الحساب:

دالة تدوير_يمين ( عقدة_الشجرة ): """تدوير الشجرة المحددة إلى اليمين.""" يسار ، Q ، C = عقدة_الشجرة A ، P ، B = يسار إرجاع ( A ، P ، ( B ، Q ، C ))

ويمكن النظر إلى الأمر من زاوية أخرى:

دوران العقدة Q إلى اليمين:

ليكن P هو الابن الأيسر لـ Q. اجعل الابن الأيسر لـ Q هو الابن الأيمن لـ P. [عيّن والد الابن الأيمن لـ P إلى Q] اجعل الابن الأيمن لـ P هو Q. [عيّن العنصر الأب لـ Q إلى P] 

دوران العقدة P إلى اليسار:

ليكن Q الابن الأيمن لـ P. اجعل الابن الأيمن لـ P هو الابن الأيسر لـ Q. [عيّن والد الطفل الأيسر لـ Q إلى P] اجعل P هو الابن الأيسر لـ Q. [عيّن العنصر الأب لـ P إلى Q] 

جميع التوصيلات الأخرى تبقى كما هي.

توجد أيضًا دورات مزدوجة ، وهي عبارة عن تركيبات من دورات يسارية ويمينية. يمكن تعريف الدورة المزدوجة اليسارية عند النقطة X بأنها دورة يمينية عند الابن الأيمن للنقطة X متبوعة بدورة يسارية عند النقطة X؛ وبالمثل، يمكن تعريف الدورة المزدوجة اليمينية عند النقطة X بأنها دورة يسارية عند الابن الأيسر للنقطة X متبوعة بدورة يمينية عند النقطة X.

تُستخدم عمليات تدوير الأشجار في عدد من هياكل بيانات الأشجار ، مثل أشجار AVL ، وأشجار الأحمر والأسود ، وأشجار WAVL ، وأشجار Splay ، وأشجار Treaps . وهي لا تتطلب سوى وقت ثابت لأنها تحويلات محلية : فهي تعمل فقط على 5 عقد، ولا تحتاج إلى فحص بقية الشجرة.

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

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

لا تزال مسألة وجود خوارزمية ذات زمن متعدد الحدود لحساب مسافة الدوران مفتوحة ، على الرغم من أن العديد من صيغ مسألة مسافة الدوران تقبل خوارزميات ذات زمن متعدد الحدود. ^{[ 1 ] [ 2 ] [ 3 ]}

أظهر كلٌّ من دانيال سليتور وروبرت تارجان وويليام ثورستون أن مسافة الدوران بين أي شجرتين مكونتين من n عقدة (لـ n ≥ 11) لا تتجاوز 2n - 6 ، وأن بعض أزواج الأشجار تكون على هذه المسافة بمجرد أن تصبح n كبيرة بما فيه الكفاية. ^{[ 4 ]} كما أظهر ليونيل بورنين أن هذه الأزواج موجودة بالفعل كلما كانت n ≥ 11. ^{[ 5 ]}  

• شجرة AVL ، وشجرة الأحمر والأسود ، وشجرة splay ، هي أنواع من هياكل بيانات شجرة البحث الثنائية التي تستخدم عمليات التدوير للحفاظ على التوازن.
• خاصية التجميع في العملية الثنائية تعني أن إجراء تدوير الشجرة عليها لا يغير النتيجة النهائية.
• تقوم خوارزمية Day –Stout–Warren بموازنة شجرة بحث ثنائية غير متوازنة.
• شبكة تاماري ، وهي مجموعة مرتبة جزئيًا يمكن تعريف عناصرها على أنها أشجار ثنائية ويتم تحديد الترتيب بين العناصر عن طريق دوران الشجرة.

• برنامج تعليمي حول تدوير شجرة AVL (RTF) من تأليف جون هارجروف