شجرة (هياكل بيانات)

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

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

شجرة
معلومات عامة
صنف فرعي من
اشتق من
شجرة غير مصنفة تحتوي على قيم متكررة (مثل القيمة 5)
العُقدة 6 هي عقدة فرعية من منظور العقدة 7، كما أنها أيضا عقدة أصلية من منظور العقدة 11
جميع العُقد متفرعة عن غيرها عدا العقد العُليا (الدائرة الحمراء) وتُسمى عقدة الجذر، وهي رأس الشجرة

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

التطبيقات

عدل

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

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

  • التسلسل الهرمي الرياضي
  • المسارات

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

المصطلحات

عدل

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

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

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

عدل
شجرة مبسطة
ليست شجرة لاشتراك أكثر من عقدة أصلية في نفس العقدة الفرعية
ليست شجرة لعدم اتصال بعض العقد، ووجود أكثر من عقدة جذرية. A→B و C→D→E

العمليات الشائعة علي هيكل الشجرة

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

طرق الفحص والبحث

عدل

يبدأ فحص عقد الشجرة (والذي يُعرف أيضا بالتجول في عقد الشجرة) من اليسار إلى اليمين وبطرق مختلفة، تختلف حسب ترتيب فحص العقدة الأصلية بالنسبة للعقدتين المتفرعتين منها، والطرق المعروفة هي:

  • الفحص السابق الترتيب: العقدة الأصلية ⬅ العقدة الفرعية اليسرى ⬅ العقدة الفرعية اليمينى.
  • الفحص الوسط الترتيب: العقدة الفرعية اليسرى ⬅ العقدة الأصلية ⬅ العقدة الفرعية اليمينى
  • الفحص اللاحق الترتيب: العقدة الفرعية اليسرى ⬅ العقدة الفرعية اليمينى ⬅ العقدة الأصلية

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

التمثيل في الذاكرة

عدل

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

أنظر أيضا

عدل

مراجع

عدل
  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.