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