شجرة (هياكل بيانات)
لمعانٍ أخرى، طالع شجرة (توضيح).
.svg)
العُقدة 6 هي عقدة فرعية من منظور العقدة 7، كما أنها أيضا عقدة أصلية من منظور العقدة 11
جميع العُقد متفرعة عن غيرها عدا العقد العُليا (الدائرة الحمراء) وتُسمى عقدة الجذر، وهي رأس الشجرة
الشجرة في سياق علوم الحاسب هي أحد أشهر أنواع هياكل البيانات، تأخذ شكل هرمي مكون من عُقد تتصل جميعا ببعضها البعض، وتُعتبر العُقدة أصلية بالنسبة لما اتصل بها من أسفل وتُعتبر فرعية بالنسبة لما اتصل بها من أعلى (انظر الشكل المقابل)، وترتبط كل عقدة أصلية بعقدة فرعية واحدة أو أكثر حسب نوع الشجرة[1]، وجميع العُقد الفرعية متصلة بعُقد أصلية باستثناء عقدة الجذر، التي تمثل رأس الشجرة أو العقدة العليا في التسلسل الهرمي للشجرة. وهذا التصميم يضمن عدم وجود حلقات أو دوائر في الشجرة، وبذلك يُمكن لتقنية العودية أن تمسح (تفحص) هيكلة الشجرة.
تُسمى الشجرة التي يتفرع فيها من كل عقدة أصلية عقدتين فرعيتين بحد أقصى باسم الشجرة الثنائية، وهي أكثر الأنواع استخداما، وبترتيب درجة العُقد الفرعية تُصبح الشجرة مرتبة من منظور نظرية الرسم البياني.
التطبيقات
[عدل]يُستخدم هيكل الشجرة لتمثيل البيانات الهرمية الشكل ومعالجتها في عدد من التطبيقات مثل:
- نظام الملفات في:
- هيكل الدليل المستخدم لتنظيم الدلائل الفرعية والملفات
- الآلية المستخدمة لتخصيص وربط كتل البيانات الموجودة على جهاز التخزين
- التسلسل الهرمي للأصناف (أو شجرة الوراثة) الذي يوضح العلاقة بين الأصناف في البرمجة كائنية التوجه.
- شجرة النحو المجرد للغات الحاسب
- معالجة اللغة الطبيعية في:
- شجرة التحليل
- نمذجة الكلام في النحو التوليدي
- شجرة الحوار لتوليد المحادثات
- نماذج كائنات المستند لمستندات لغة التوصيف القابلة للتوسعة ولغة توصيف النص الفائق
- شجرة البحث التي تُخزن البيانات بطريقة تُمكن خوارزميات البحث من مسح هيكلة الشجرة بشكل فعال، وأشهرها شجرة البحث الثنائية
- تمثيل خوارزميات الترتيب
- الصور المولدة بالحاسب
- أشجار محاكاة بارنز هت المستخدمة في محاكاة المجرات
- تمثل الأكوام (إحدى أشكال هياكل البيانات)
- التصنيفات الهرمية مثل تصنيف ديوي العشري
- البرمجة الوراثية
- التجميع الهرمي
كما يمكن استخدام هيكل الشجرة لتمثيل ومعالجة الهياكل الرياضية المختلفة، مثل:
- التسلسل الهرمي الرياضي
- المسارات
كما تُستخدم الهياكل الشجرية لرسم خرائط العلاقات بين الأشياء، مثل:
- المكونات الأصلية والفرعية في رسم العرض التفصيلي
- استدعاءات الدالة الفرعية
- وراثة الحمض النووي في الكائنات الحية
المصطلحات
[عدل]تُمثل العقدة حيز أو مكان لحفظ البيانات، وتتصل العُقدة بمثيلاتها (العقد الأخرى) بروابط تسمى أحيانًا الحواف. ويُمكن أن يتفرع من كل عقدة عند أسفلها عدد من العقد تُسمى بالعقد الفرعية (أو عقدة الابن) وتُعرف حينها عقدة الأصل بالعقدة الأصلية (أو عقدة الأب)، وتسمى العقد الفرعية من نفس الأصل بالعُقد الشقيقة، وعادةً ما تكون مرتبة من اليسار إلى اليمين، وجميع العقد متفرعة من غيرها عدا العقدة الجذرية أو عقدة الجذر. كما يمكن تقسيم العقد إلى داخلية وخارجية حسب وجود تفريع، فالعقدة التي يتفرع منها عقد أخرى تُسمى عقدة داخلية، أما العقدة التي لا يتفرع منها أي عقد فتسمى عقدة خارجية (المعروفة أيضًا باسم العقدة الطرفية أو العقد الورقية). ويُمثَل ارتفاع أي عقدة بطول أقصى مسار بينها وبين العقدة الطرفية، فيما يُمثَل عمق أي عقدة بطول أقصى مسار بينها وبين عقدة الجذر. وبالتالي فإن عمق عقدة الجذر يساوي صفر، وارتفاع العقد الورقية يساوي صفر.، وتشمل المصطلحات الأخرى المستخدمة ما يلي:
- الجار: عقدة الأصل أو الفرع منها
- السلف: أصول أي عقدة الفرعية انتهاءا لعقدة الجذر.
- الخلف: فروع أي عقدة أصلية انتهاء إلى العقد الطرفية
- درجة العقدة: تحدد بعدد العقد الفرعية لها
- درجة الشجرة: أقصى عدد متاح للعقد الفرعية المحتملة لأصل واحد
- المسافة: عدد حواف أقصر مسار بين عقدتين.
- مستوى العقدة: عدد حواف أقصر مسار بينها وبين عقدة الجذر. وهو نفسه.
- العرض: عدد العقد في المستوى.
- السعة: عدد الأوراق
- الشجرة المرتبة: شجرة تُرتب فيها العقد الفرعية بنظام معين.
- حجم الشجرة: عدد العقد الكلية للشجرة.
أمثلة على هيكل الشجرة وغيرها
[عدل]
العمليات الشائعة علي هيكل الشجرة
[عدل]- تعداد جميع العقد أو جزء منها
- البحث عن عقدة
- إضافة عقدة جديد في موضع معين على الشجرة
- حذف عقدة
- التقليم : إزالة جزء كامل من الشجرة
- التطعيم : إضافة قسم كامل إلى شجرة
- العثور على العقدة الأصلية لأي عقدة فرعية
- العثور على الأصل المشترك لعقدتين فرعيتين
طرق الفحص والبحث
[عدل]يبدأ فحص عقد الشجرة (والذي يُعرف أيضا بالتجول في عقد الشجرة) من اليسار إلى اليمين وبطرق مختلفة، تختلف حسب ترتيب فحص العقدة الأصلية بالنسبة للعقدتين المتفرعتين منها، والطرق المعروفة هي:
- الفحص السابق الترتيب: العقدة الأصلية ⬅ العقدة الفرعية اليسرى ⬅ العقدة الفرعية اليمينى.
- الفحص الوسط الترتيب: العقدة الفرعية اليسرى ⬅ العقدة الأصلية ⬅ العقدة الفرعية اليمينى
- الفحص اللاحق الترتيب: العقدة الفرعية اليسرى ⬅ العقدة الفرعية اليمينى ⬅ العقدة الأصلية
كما يمكن البحث عن عقدة معينة في الشجرة باستخدام خوارزمية بحث الاتساع أولا، حيث تبدأ الخوارزمية البحث من عقدة الجذر ثم عقد المستوى التالى حتى إنهائه ثم الانتقال للمستوى الذي يليه، حتى انتهاء بحث جميع المستويات وجميع عقد الشجرة. أو باستخدام خوارزمية بحث العمق أولا، التي تبدأ البحث من عقدة الجذر إلى أقصى عمق أولا ثم إلى العمق الذي يليه، حتى انتهاء بحث جميع عقد الشجرة.
التمثيل في الذاكرة
[عدل]هناك العديد من الطرق المختلفة لتمثيل الأشجار في الذاكرة العاملة، وعادةً ما يتم تخصيص سجلات ديناميكية تشير لمكان العقد الأصلية لها أو الفرعية منها أو كليهما، وإذا كان حجمها ثابتًا فيمكن تخزينها في قائمة. وتُمثل عقد الشجرة في قواعد البيانات العلائقية على شكل صفوف جدول، مع معرفات الصفوف المفهرسة لتسهيل المؤشرات بين العقد الأصلية والفرعية. كما يمكن أيضًا تخزين العقد كعناصر في مصفوفة حاسوبية، مع تحديد العلاقات بين عقدها حسب مواقعها في المصفوفة (كما في الكومة).
أنظر أيضا
[عدل]- هياكل بيانات
- تصنيف: أشجار (هياكل البيانات) (أنواع كتالوجات الأشجار الحسابية)
مراجع
[عدل]- ^ Subero، Armstrong (2020). "3. Tree Data Structure". Codeless Data Structures and Algorithms. Berkeley, CA: Apress. DOI:10.1007/978-1-4842-5725-8. ISBN:978-1-4842-5724-1.
A parent can have multiple child nodes. ... However, a child node cannot have multiple parents. If a child node has multiple parents, then it is what we call a graph.
