يستخدم مصطلح الشجرة في تراكيب البيانات لتمثيل بعض البيانات بطريقة مماثلة للشجرة الفعلية و لذلك بعد اختراع الحاسوب وجد المبرمجون أن أفضل طريقة لتمثيل بعض البيانات داخل ذاكرة الحاسوب هي طريقة الشجرة ، سوف نتعرف من خلال هذا البحث استخدامات الأشجار و خاصة الثنائية في علم الحاسوب .
تعريف الأشجار في علوم الحاسوب :
مفهوم الشجرة : هي مجموعة منتهية مكونة من عقدة أو أكثر بحيث تحقق :
1- يوجد عقدة مصممة بشكل خاص تدعى جذر الشجر(Root)
2- العقد المتبقية تجزأ الى n أكبر أو يساوي الصفر من المجموعات المنفصلة T1 , T2 , ..... Tn حيث كل مجموعة من هذه المجموعات تشكل شجرة و تدعى المجموعات أشجاراً فرعية (Sub-Trees) من عقدة الجذر .
في علوم الكمبيوتر ، تعد "الشجرة" نوعاً من البيانات المجردة المستخدمة على نطاق واسع (ADT) - أو بنية بيانات تنفذ هذه ADT - التي تحاكي بنية شجرة هرمية ، مع قيمة الجذر ومجموعات فرعية من الأطفال ذوي العقدة الأصل ، ويتم تمثيلها كمجموعة من العقد المرتبطة.
يمكن تعريف بنية بيانات الشجرة بشكل متكرر على أنها مجموعة من العقد (تبدأ من عقدة الجذر) ، حيث تكون كل عقدة بنية بيانات تتكون من قيمة ، إلى جانب قائمة من الإشارات إلى العقد ("الأطفال") ، مع القيود التي يتم تكرار أي مرجع ، ولا شيء يشير إلى الجذر.
بدلاً من ذلك ، يمكن تعريف الشجرة بشكل مجردة ككل (عالمياً) كشجرة مرتبة ، مع تعيين قيمة لكل عقدة .
كلا المنظورين مفيدان : بينما يمكن تحليل الشجرة رياضياً ككل ، عندما يتم تمثيلها فعلياً كهيكل بيانات ، عادةً ما يتم تمثيلها و معالجتها بشكل منفصل عن طريق العقدة (بدلاً من مجموعة من العقد و قائمة متقاربة من الحواف بين العقد ، كما يمكن للمرء أن يمثل الرسم ) . على سبيل المثال :
عند النظر إلى شجرة ككل ، يمكن للمرء أن يتحدث عن "العقدة الأصل" لعقدة معينة ، ولكن بشكل عام باعتبارها بنية بيانات ، تحتوي العقدة المحددة فقط على قائمة أطفالها ، ولكنها لا تحتوي على إشارة الى الأم (إن وجدت) .
اذاً الشجرة هي مجموعة من الكيانات تسمى العقد ، ترتبط العقد بوساطة الحواف ، و تحتوي كل عقدة على قيمة أو بيانات ، و قد تحتوي أو لا تحتوي على عقدة فرعية ، تسمى العقدة الأولى من الشجرة الجذر و اذا كانت هذه العقدة الجذرية متصلة بعقدة أخرى ، فإن الجذر هو العقدة الأصلية و العقدة المتصلة هي طفل ، جميع العقد شجرة متصلة من قبل الروابط تسمى الحواف ، إنه جزء مهم من الأشجار ، لأنه يدير العلاقة بين العقد ، الأوراق هي العقد الأخيرة على شجرة و هي العقدة بدون أطفال مثل الأشجار الحقيقية لدينا الجذر والفروع وأخيرا الأوراق .
مفاهيم مهمة أخرى لفهم الطول والعمق :
ارتفاع الشجرة هو طول أطول طريق إلى ورقة.
عمق العقدة هو طول المسار إلى جذرها.
التطبيقات العملية للشجرة :
- يمكن استخدام الأشجار لتخزين البيانات التي لها بنية هرمية متأصلة . على سبيل المثال : قد يستخدم نظام التشغيل شجرة للأدلة و الملفات و المجلدات في نظام إدارة الملفات الخاصة به .
- إنها ديناميكية ، مما يعني أنه من السهل إضافة وحذف العقد .
- إنها سهلة البحث والفرز باستخدام خوارزميات اجتياز قياسية .
- يمكن استخدامها لمعالجة بناء جملة العبارات باللغات الطبيعية ولغات البرمجة بحيث يتم استخدامها بشكل شائع عند تجميع كود البرمجة .
- جذر Root : العقدة العلوية في الشجرة
- الطفل Child : عقدة متصلة مباشرة بعقدة أخرى عند الابتعاد عن الجذر
- الوالد Perant : مفهوم العكس للطفل
- الأشقاء Siblings : مجموعة من العقد مع نفس الوالد
- السليل Dercendant : العقدة قابلة للوصول عن طريق المتابعة المتكررة من الأب إلى الطفل. المعروف أيضا باسم subchild.
- السلف Ancestor : عقدة يمكن الوصول إليها عن طريق المتابعة المتكررة من طفل لآب.
- ليف laef : العقدة الخارجية (غير شائعة) عقدة بدون أطفال.
- العقدة الفرعية Branch node , العقدة الداخلية Internal node : العقدة التي لها طفل واحد على الأقل.
- الدرجة Degree : للحصول على عقدة معينة ، وعدد الأطفال. ورقة هي بالضرورة درجة الصفر.
- حافة Edge : الاتصال بين عقدة واحدة وأخرى.
- المسار Path : تسلسل العقد والحواف التي تربط العقدة بأحد السليل.
- المستوى Level : يتم تعريف مستوى العقدة على النحو التالي: 1 + عدد الحواف بين العقدة و الجذر
- العمق Depth : يتم تعريف عمق العقدة على النحو التالي: عدد الحواف بين العقدة والجذر.
- ارتفاع العقدة Height of node : ارتفاع العقدة هو عدد الحواف على أطول مسار بين هذه العقدة وورقة السليل.
- ارتفاع الشجرة Height of tree : ارتفاع الشجرة هو ارتفاع عقدة الجذر.
- الغابة Forest : الغابة عبارة عن مجموعة من أشجار مفككة .. n أكبر أو يساوي الصفر
الاستعمالات الشائعة :
- التلاعب الهرمي بالبيانات
- جعل المعلومات سهلة البحث
- التلاعب بقوائم الترتيب من البيانات
- خوارزميات التوجيه
العمليات الشائعة :
تعداد كافة العناصر ، تعداد جزء من شجرة ، البحث عن عنصر ، إضافة عنصر جديد في موقع معين على الشجرة ، حذف عنصر ، إزالة مقطع كامل من شجرة (تسمى التلقيم) ، إضافة قسم كامل لشجرة (تسمى التطعيم) ، العثور على الجذر لأي رأس .
الأشجار الثنائية :
الآن سنناقش نوعاً معيناً من الأشجار . نحن نسميها الشجرة الثنائية و هي نوع من أنواع تمثيل البيانات و يتكون من مكونين أساسيين هما العقد (NODES) و الأغصان (ARCS) ، عندما نقوم بتمثيل هذه الشجرة فإننا نقلب مفهومها ، فيكون الجذر في الأعلى و الأغصان في الأسفل .
و من هذه الأشجار : الشجرة الثنائية التامة ، الشجرة الثنائية الخطية ، الشجرة الثنائية الكاملة ، شجرة البحث الثنائية .
أشجار البحث الثنائية : أشجار البحث الثنائية تدعم استخدام عمليات البحث عن عنصر ، إضافة عنصر ، حذف عنصر .
أشجار البحث الثنائية : أشجار البحث الثنائية تدعم استخدام عمليات البحث عن عنصر ، إضافة عنصر ، حذف عنصر .
في علم الكمبيوتر ، الشجرة الثنائية هي بنية بيانات شجرة تحتوي كل عقدة على أكثر من طفلين ، ويشار إليهما بالطفل الأيسر والطفل الأيمن.
