شجرة (بنية بيانات)

(بالتحويل من شجرة بيانية)

في علم الحاسوب, الشجرة هي هيكل بيانات واسع الاستخدام يحاكي شكل شجرة هرمية مع مجموعة من الرؤوس المرتبطة.

شجرة (بنية بيانات)
شجرة بسيطة غير مرتبة، العقدة رقم 7 لديها ابنين 2 و6 وأب واحد 2. العقدة الجذر ليس لديها أب.

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

مصطلحات

عدل

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

رأس داخلي أو رأس باطني هو أي رأس من الشجرة بحيث يمتلك رؤوس أبناء. وبالمثل, رأس خارجي (أيضا يطلع عليه ورقة أو رأس طرفي) هو أي رأس بحيث لا يمتلك أية رؤوس أبناء.

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

شجرة حرة هي الشجرة التي ليس لها جذر.

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

شجرة فرعية لشجرة ج هي شجرة تتكون من رأس في الشجرة ج وكل أحفاده في ج. (هذا تعريف مختلف عن التعريف الرسمي للشجرة الفرعية في نظرية المخططات[1]). شجرة فرعية التي تبدأ من الجذر هي الشجرة الكاملة؛ الشجرة الفرعية التي تبدأ من أي رأس اخر تسمى شجرة فرعية حقيقية (مشابها لمصطلح المجموعة الجزئية الحقيقية).

تمثيل

عدل

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

الشجر والرسوم البيانية

عدل

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

العلاقة مع الشجر في نظرية المخططات

عدل

في نظرية المخططات، الشجرة هي رسم بياني متصل عديم الحلقات؛ إلا إذا نص غير ذلك، الشجر والرسوم البيانية غير متصلة.

طرق الاجتياز

عدل

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

عمليات شائعة

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

استعمالات شائعة

عدل

انظر أيضًا

عدل

Other trees

عدل

المراجع

عدل
  1. ^ Eric W. Weisstein "Subtree." From MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/Subtree.html نسخة محفوظة 2020-04-26 على موقع واي باك مشين.
  2. ^ Miltiadou, Milto; Campbell, Neill D. F.; Cosker, Darren; Grant, Michael G. (Jan 2021). "A Comparative Study about Data Structures Used for Efficient Management of Voxelised Full-Waveform Airborne LiDAR Data during 3D Polygonal Model Creation". Remote Sensing (بالإنجليزية). 13 (4): 559. Bibcode:2021RemS...13..559M. DOI:10.3390/rs13040559.