شجرة ثنائية مترابطة

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة
شجرة متشابكة ، مع روابط التشابك الخاصة الموضحة بأسهم متقطعة

في مجال الحوسبة ، الشجرة الثنائية المترابطة هي نوع من أنواع الأشجار الثنائية التي تسهل عملية الاجتياز بترتيب معين.

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

عملية ربط الخيوط

"يتم ربط الشجرة الثنائية عن طريق جعل جميع مؤشرات الأبناء الأيمن التي عادة ما تكون فارغة تشير إلى العقدة التالية في الترتيب ( إن وجدت)، وجميع مؤشرات الأبناء الأيسر التي عادة ما تكون فارغة تشير إلى العقدة السابقة في الترتيب." [ 1 ]

يفترض هذا أن ترتيب اجتياز الشجرة هو نفسه ترتيب الاجتياز الداخلي. مع ذلك، يمكن إضافة مؤشرات إلى عقد الشجرة بدلاً من استبدالها. تُعرف القوائم المتصلة المُعرَّفة بهذه الطريقة باسم "الخيوط"، ويمكن استخدامها لتمكين الاجتياز بأي ترتيب مطلوب. على سبيل المثال، قد تُرتَّب شجرةٌ تُمثِّل عقدها معلوماتٍ عن أشخاصٍ حسب الاسم، ولكن مع خيوطٍ إضافيةٍ تُتيح الاجتياز السريع حسب تاريخ الميلاد أو الوزن أو أي سمةٍ أخرى معروفة.

تحفيز

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

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

خوارزمية traverse( t ):

  • المدخلات: مؤشر t إلى عقدة (أو nil )
  • إذا كانت قيمة t تساوي nil ، فقم بالعودة.
  • آخر:
    • traverse(left-child( t ))
    • قم بزيارة
    • traverse(right-child( t ))

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

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

في كتاب مدرسي صدر عام 1968، تساءل دونالد كنوث عما إذا كانت هناك خوارزمية غير تكرارية لاجتياز الشجرة بترتيبها الداخلي، لا تستخدم مكدسًا ولا تُجري أي تعديلات على الشجرة. [ 2 ] أحد حلول هذه المشكلة هو ترابط الشجرة، الذي قدمه جوزيف م. موريس عام 1979. [ 3 ] [ 4 ] في الطبعة اللاحقة الصادرة عام 1969، [ 5 ] نسب كنوث تمثيل الشجرة المترابطة إلى بيرليس وثورنتون (1960). [ 6 ]

العلاقة بمؤشرات الأصل

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

من الممكن أيضًا اكتشاف العقدة الأب لعقدة ما من شجرة ثنائية مترابطة، دون استخدام مؤشرات العقدة الأب أو مكدس البيانات بشكل صريح، على الرغم من أن هذه الطريقة أبطأ. لتوضيح ذلك، لنفترض عقدة k لها ابن أيمن r . عندئذٍ، يجب أن يكون المؤشر الأيسر لـ r إما ابنًا أو خيطًا يشير إلى k . في حالة وجود ابن أيسر لـ r ، يجب أن يكون لهذا الابن الأيسر بدوره إما ابن أيسر خاص به أو خيط يشير إلى k ، وهكذا بالنسبة لجميع الأبناء اليساريين المتتاليين. لذا، بتتبع سلسلة المؤشرات اليسرى من r ، سنجد في النهاية خيطًا يشير إلى k . الوضع مشابه تمامًا عندما تكون q هي الابن الأيسر لـ p ، حيث يمكننا تتبع الأبناء الأيمنين لـ q إلى خيط يشير إلى p .

في لغة بايثون :

دالة parent ( node ) : إذا كانت node هي node.tree.root : أرجع None x = node y = node بينما صحيح : إذا كان y خيطًا : p = y.right إذا كان p يساوي None أو p.left ليس node : p = x بينما ليس y خيطًا : p = p.left p = p.left أرجع p وإذا كان x خيطًا : p = x.left إذا كان p يساوي None أو p.right ليس node : p = y بينما ليس y خيطًا : p = p.right p = p.right أرجع p x = x.left y = y.right​​​​​​​​​​​​​​​​​​​​​​​​​​​​

الأنواع

  1. أحادي الخيط: يتم توجيه كل عقدة إما نحو العقدة السابقة أو اللاحقة لها في الترتيب (يسارًا أو يمينًا).
  2. مزدوج الخيوط: يتم ربط كل عقدة بالعقدة السابقة واللاحقة لها في الترتيب (يسارًا ويمينًا ).

مجموعة اجتياز الترتيب الداخلي

تُشير الخيوط إلى العناصر السابقة واللاحقة للعقدة وفقًا لعملية اجتياز ترتيبية.

الترتيب الداخلي للشجرة المترابطة هو A,B,C,D,E,F,G,H,I، والسابق لـ Eهو D، واللاحق لـ Eهو F.

مثال

لنقم بإنشاء شجرة ثنائية مترابطة من شجرة ثنائية عادية:

الترتيب الداخلي للشجرة المذكورة أعلاه هو — DBAE C. لذا، ستكون شجرة الخيوط الثنائية المقابلة هي —

في شجرة ثنائية مترابطة ذات m اتجاه مع n عقدة، يوجد n × m − ( n −1) رابط فارغ.

مراجع

  1. ↑ فان ويك، كريستوفر ج. هياكل البيانات وبرامج لغة سي ، أديسون-ويسلي، 1988، ص 175. ISBN 978-0-201-16116-8.
  2. ↑ كنوت، دي إي (1968). الخوارزميات الأساسية . فن برمجة الحاسوب. المجلد 1 ( الطبعة الأولى). ريدينغ/ماساتشوستس: أديسون ويسلي.  
  3. ↑ موريس، جوزيف هـ. (1979). "اجتياز الأشجار الثنائية ببساطة وبتكلفة منخفضة". رسائل معالجة المعلومات . 9 (5). doi : 10.1016/0020-0190(79)90068-1 .
  4. ↑ ماتيتي، برابهاكر؛ مانغيرمالاني، رافي (1988). "إعادة النظر في خوارزمية موريس لاجتياز الشجرة". علم برمجة الحاسوب . 11 : 29-43 . doi : 10.1016/0167-6423(88)90063-9 .
  5. ↑ كنوت، دي إي (1969). الخوارزميات الأساسية . فن برمجة الحاسوب. المجلد 1 ( الطبعة الثانية). أديسون ويسلي.  Hre: Sect.2.3.1 "اجتياز الأشجار الثنائية".
  6. ↑ بيرليس، آلان جاي؛ ثورنتون، سي. (أبريل 1960). "معالجة الرموز بواسطة القوائم المترابطة" . اتصالات رابطة آلات الحوسبة . 3 (4): 195-204 . doi : 10.1145/367177.367202 .