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

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

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

مصطلحات

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

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

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

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

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

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

تمثيل

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

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

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

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

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

طرق الاجتياز

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