شجرة ثنائية
| صنف فرعي من | |
|---|---|
| يدرسه |
 | تحتوي هذه المقالة اصطلاحات معربة غير مُوثَّقة. لا تشمل ويكيبيديا العربية الأبحاث الأصيلة، ويلزم أن تُرفق كل معلومة فيها بمصدر موثوق به. (أكتوبر 2015) |
الشجرة الثنائية في علوم الحاسب هي هيكل بيانات على شكل شجرة ثنائية العُقد الفرعية، أي أن كل عقدة أصلية يخرج منها عقدتان فرعيتان على الأكثر، الأولى تسمى العقدة الفرعية اليسرى، والثانية تسمى العقدة الفرعية اليمنى، [1][2][3]وتُستخدم الشجرة الثنائية في شجرة البحث الثنائية والأكوام الثنائية.
المصطلحات
[عدل]تُمثل العقدة حيز أو مكان لحفظ البيانات، وتتصل العُقدة بمثيلاتها (العقد الأخرى) بروابط تسمى أحيانًا الحواف. ويُمكن أن يتفرع من كل عقدة عند أسفلها عدد من العقد تُسمى بالعقد الفرعية (أو عقدة الابن) وتُعرف حينها عقدة الأصل بالعقدة الأصلية (أو عقدة الأب)، وتسمى العقد الفرعية من نفس الأصل بالعُقد الشقيقة، وعادةً ما تكون مرتبة من اليسار إلى اليمين، وجميع العقد متفرعة من غيرها عدا العقدة الجذرية أو عقدة الجذر. كما يمكن تقسيم العقد إلى داخلية وخارجية حسب وجود تفريع، فالعقدة التي يتفرع منها عقد أخرى تُسمى عقدة داخلية، أما العقدة التي لا يتفرع منها أي عقد فتسمى عقدة خارجية (المعروفة أيضًا باسم العقدة الطرفية أو العقد الورقية). ويُمثَل ارتفاع أي عقدة بطول أقصى مسار بينها وبين العقدة الطرفية، فيما يُمثَل عمق أي عقدة بطول أقصى مسار بينها وبين عقدة الجذر. وبالتالي فإن عمق عقدة الجذر يساوي صفر، وارتفاع العقد الورقية يساوي صفر.، وتشمل المصطلحات الأخرى المستخدمة ما يلي:
- الجار: عقدة الأصل أو الفرع منها
- السلف: أصول أي عقدة الفرعية انتهاءا لعقدة الجذر.
- الخلف: فروع أي عقدة أصلية انتهاء إلى العقد الطرفية
- درجة العقدة: تحدد بعدد العقد الفرعية لها
- درجة الشجرة: أقصى عدد متاح للعقد الفرعية المحتملة لأصل واحد
- المسافة: عدد حواف أقصر مسار بين عقدتين.
- مستوى العقدة: عدد حواف أقصر مسار بينها وبين عقدة الجذر. وهو نفسه.
- العرض: عدد العقد في المستوى.
- السعة: عدد الأوراق
- الشجرة المرتبة: شجرة تُرتب فيها العقد الفرعية بنظام معين.
- حجم الشجرة: عدد العقد الكلية للشجرة.
انظر أيضا
[عدل]مراجع
[عدل]- ^ "معلومات عن شجرة ثنائية على موقع mathworld.wolfram.com". mathworld.wolfram.com. مؤرشف من الأصل في 2018-11-21.
- ^ "معلومات عن شجرة ثنائية على موقع xlinux.nist.gov". xlinux.nist.gov. مؤرشف من الأصل في 2018-10-13.
- ^ "معلومات عن شجرة ثنائية على موقع babelnet.org". babelnet.org. مؤرشف من الأصل في 2019-12-09.
- Donald Knuth. The art of computer programming vol 1. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3, especially subsections 2.3.1–2.3.2 (pp. 318–348).
- Kenneth A Berman, Jerome L Paul. Algorithms: Parallel, Sequential and Distributed. Course Technology, 2005. ISBN 0-534-42057-5. Chapter 4. (pp. 113–166).
