شجرة (نوع بيانات مجرد)

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

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

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

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

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

مصطلحات

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

العقدة الداخلية (وتُعرف أيضًا بالعقدة الفرعية أو عقدة الفرع ) هي أي عقدة في الشجرة لها عقد فرعية. وبالمثل، فإن العقدة الخارجية (وتُعرف أيضًا بالعقدة الطرفية أو عقدة الورقة ) هي أي عقدة ليس لها عقد فرعية.

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

يمكن اعتبار كل عقدة غير جذرية بمثابة العقدة الجذرية لشجرتها الفرعية الخاصة ، والتي تشمل تلك العقدة وجميع فروعها. [ أ ] [ 3 ]

مصطلحات أخرى تُستخدم مع الأشجار:

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

العمليات المشتركة

  • حصر جميع العناصر
  • تعداد جزء من شجرة
  • البحث عن عنصر
  • إضافة عنصر جديد في موضع معين على الشجرة
  • حذف عنصر
  • التقليم : إزالة جزء كامل من الشجرة
  • التطعيم : إضافة قسم كامل إلى الشجرة
  • إيجاد جذر أي عقدة
  • إيجاد السلف المشترك الأدنى لعقدتين

أساليب الاجتياز والبحث

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

التمثيلات

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

يمكن أيضًا تخزين العقد كعناصر في مصفوفة ، مع تحديد العلاقات بينها من خلال مواقعها في المصفوفة (كما هو الحال في الكومة الثنائية ).

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

يمكن ترميز الأشجار المرتبة بشكل طبيعي بواسطة متواليات محدودة، على سبيل المثال باستخدام الأعداد الطبيعية. [ 5 ]

أمثلة على الأشجار وغير الأشجار

ليست شجرة : جزآن غير متصلين ، A→B و C→D→E. يوجد أكثر من جذر واحد.
ليست شجرة : دورة غير موجهة 1-2-4-3. 4 لها أكثر من أب واحد (حافة واردة).
ليست شجرة : دورة B→C→E→D→B. B لها أكثر من أب واحد (حافة واردة).
ليست شجرة : دورة A→A. A هي الجذر ولكن لها أيضًا أب.
كل قائمة خطية هي شجرة بشكل بديهي .

نظرية الأنواع

كنوع بيانات مجرد ، يتم تعريف نوع الشجرة المجرد T بقيم من نوع E ، باستخدام نوع الغابة المجرد F (قائمة الأشجار)، بواسطة الدوال التالية:

القيمة: T → E
الأطفال: ص → خ
لا شيء: () → F
العقدة: هـ × و → ت

مع البديهيات:

قيمة (العقدة ( هـ ، و )) = هـ
children(node( e , f )) = f

من حيث نظرية الأنواع ، فإن الشجرة هي نوع استقرائي محدد بواسطة المنشئين nil (غابة فارغة) و node (شجرة ذات عقدة جذرية بقيمة معينة وأبناء).

المصطلحات الرياضية

بشكل عام، تُعتبر بنية بيانات الشجرة شجرة مُرتبة ، وعادةً ما تُرفق قيم بكل عقدة. وبشكلٍ أدق، فهي (إذا كان مطلوبًا أن تكون غير فارغة):

  • شجرة متجذرة باتجاه "بعيد عن الجذر" (مصطلح أضيق هو " التفرع الشجري ")، بمعنى:
    • الرسم البياني الموجه ،
    • الرسم البياني الأساسي غير الموجه عبارة عن شجرة (أي رأسين متصلين بمسار بسيط واحد فقط)، [ 6 ]
    • مع جذر مميز (يتم تحديد رأس واحد كجذر)،
    • والذي يحدد الاتجاه على الحواف (تشير الأسهم بعيدًا عن الجذر؛ عند إعطاء حافة، تسمى العقدة التي تشير إليها الحافة بالعقدة الأصلية وتسمى العقدة التي تشير إليها الحافة بالعقدة الفرعية )، بالإضافة إلى:
  • ترتيب على العقد الفرعية لعقدة معينة، و
  • قيمة (من نوع بيانات معين) عند كل عقدة.

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

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

التطبيقات

تُستخدم الأشجار بشكل شائع لتمثيل البيانات الهرمية أو معالجتها في تطبيقات مثل:

يمكن استخدام الأشجار لتمثيل ومعالجة مختلف الهياكل الرياضية، مثل:

تُستخدم الهياكل الشجرية غالبًا لرسم العلاقات بين الأشياء، مثل:

يمكن اعتبار مستندات JSON و YAML بمثابة أشجار، ولكن يتم تمثيلها عادةً بواسطة قوائم وقواميس متداخلة .

انظر أيضاً

ملحوظات

  1. ↑ يختلف هذا عن التعريف الرسمي للشجرة الفرعية المستخدم في نظرية الرسوم البيانية، وهي رسم بياني فرعي يُشكل شجرة - ولا يشترط أن يشمل جميع الفروع الفرعية. على سبيل المثال، تُعد العقدة الجذرية بحد ذاتها شجرة فرعية بالمعنى النظري للرسوم البيانية، ولكن ليس بالمعنى المتعلق ببنية البيانات (إلا إذا لم يكن هناك فروع فرعية).

مراجع

  1. ↑ سوبيرو، أرمسترونغ (2020). "3. بنية بيانات الشجرة". هياكل البيانات والخوارزميات بدون كتابة أكواد . بيركلي، كاليفورنيا: أبريس. doi : 10.1007/978-1-4842-5725-8 . ISBN 978-1-4842-5724-1يمكن أن يكون للعقدة الأب عدة عقد فرعية. ... مع ذلك، لا يمكن أن يكون للعقدة الفرعية أكثر من عقدة أب. إذا كان للعقدة الفرعية أكثر من عقدة أب، فإنها تُسمى حينها رسمًا بيانيًا.
  2. ↑ "الشجرة المجردة / نوع البيانات المجردة للشجرة | أنواع البيانات المجردة | ECE 250 | جامعة واترلو" . ece.uwaterloo.ca . تاريخ الاسترجاع: 13 ديسمبر 2024 .
  3. ↑ وايسشتاين، إريك دبليو. "الشجرة الفرعية" . عالم الرياضيات .
  4. ↑ سوزانا س. إيب (أغسطس 2010). الرياضيات المتقطعة مع التطبيقات . باسيفيك غروف، كاليفورنيا: شركة بروكس/كول للنشر. ص 694. ISBN  978-0-495-39132-6.
  5. ^ ل. أفاناسييف. بي بلاكبيرن؛ أنا ديميتريو؛ ب. جيفي؛ إي.جوريس؛ م. ماركس؛ م. دي ريكي (2005). "PDL للأشجار المرتبة" (PDF) . مجلة المنطق التطبيقي غير الكلاسيكي . 15 (2): 115-135 . دوى : 10.3166/jancl.15.115-135 . S2CID 1979330 . 
  6. ↑ ليفين، أوسكار (31 ديسمبر 2018). الرياضيات المتقطعة: مقدمة مفتوحة ( الطبعة الثالثة). أمازون ديجيتال سيرفيسز ذ.م.م. - ك.د.ب. ص 247. ISBN   978-1792901690.

للمزيد من القراءة