الشجرة هي واحدة من هياكل البيانات الرئيسية في علوم الكمبيوتر والرياضيات. إنها مجموعة من الرؤوس والحواف ، حيث تربط كل حافة رأسين. من الخصائص المهمة للشجرة أنها لا تحتوي على دورات ، أي أنه لا توجد طريقة لاجتياز حواف الشجرة والعودة إلى الرأس الأصلي.
واحدة من الميزات المثيرة للاهتمام للشجرة هي ارتباطها بالرسوم البيانية. يمكن اعتبار الشجرة كحالة خاصة للرسم البياني حيث تكون الحلقات والحواف المتعددة مفقودة. هذا يعني أنه يمكنك تمثيل الشجرة كرسم بياني ثنائي ، حيث يتم تقسيم جميع الرؤوس إلى مجموعتين تسمى الفصوص. في كل فص ، لا تكون الرؤوس متجاورة مع بعضها البعض ، أي لا توجد حواف تربط رؤوس فص واحد ببعضها البعض. يمكن أن تكون هذه الملاحظة مفيدة في البحث عن الخصائص والعمليات على الشجرة.
الخاصية الرئيسية للرسوم البيانية ثنائية الأجزاء هي أنها لا تحتوي على دورات فردية. يمكن إثبات ذلك باستخدام طريقة تلوين الرأس. إذا كان الرسم البياني ثنائي الأجزاء يحتوي على دورة ذات طول فردي ، فيمكن تلوين رؤوس هذه الدورة بلونين مختلفين (على سبيل المثال ، الأسود والأبيض). ولكن بما أن القمم المتصلة بحافة يجب أن تكون ملونة بألوان مختلفة ، فإن الحالة الثنائية تنتهك. وبالتالي ، إذا كان من الممكن تلوين الرسم البياني بلونين ، فهو ثنائي ولا يحتوي على دورات فردية. وبما أن الشجرة عبارة عن رسم بياني ثنائي بدون دورات ، فإنها ستحتوي بالضرورة على رؤوس فص واحد فقط.
إن فهم الشجرة كرسم بياني ثنائي يسمح بفهم أعمق لهيكلها والعلاقات بين عناصرها. يمكن أن تكون هذه المعرفة مفيدة في حل المشكلات المتعلقة بالأشجار ، وكذلك في تطوير خوارزميات للعمل مع بنية البيانات هذه. يوضح الدليل على أن الشجرة عبارة عن رسم بياني ثنائي مثالا توضيحيا لاستخدام طريقة تلوين الرأس في تحليل خصائص الرسم البياني.
- شجرة
- كرسم بياني ثنائي
- الإثبات والتفسير
- هيكل وخصائص
- كنموذج بيانات
- التطبيق في علوم الكمبيوتر
- تصنيف الأشجار
- خوارزميات اجتياز الأشجار
- الزحف العميق
- اجتياز العرض
- سؤال وجواب
- كيف يمكن تمثيل الشجرة كرسم بياني ثنائي?
- لماذا يمكن تمثيل الشجرة كرسم بياني ثنائي?
- ما هي ميزة تمثيل شجرة كرسم بياني ثنائي?
- ما هي العلاقة بين الرسوم البيانية الثنائية والأشجار?
شجرة
الشجرة عبارة عن بنية بيانات مجردة عبارة عن مجموعة من الرؤوس والحواف ، حيث يكون لكل رأس والد واحد بالضبط (باستثناء الجذر) ويمكن أن يكون له عدد تعسفي من الرؤوس الفرعية.
تستخدم الشجرة في العديد من مجالات علوم الكمبيوتر والبرمجة ، مثل رسومات الكمبيوتر وقواعد البيانات والخوارزميات وهياكل البيانات.
الخصائص الرئيسية للشجرة هي:
- الجذر هو رأس ليس له أصل وهو أول رأس للشجرة. كل قمة من الشجرة لها مسار من الجذر.
- الحافة هي اتصال بين رأسين من الشجرة. تنشأ الحافة من قمة الرأس الأم وتؤدي إلى قمة الرأس الفرعية.
- الورقة هي قمة لا تحتوي على رؤوس فرعية.
- المسار عبارة عن مجموعة من الحواف التي تربط رأسين لشجرة.
- الارتفاع هو الحد الأقصى لعدد الحواف في المسار من الجذر إلى أقصى قمة.
- العمق هو عدد الحواف على المسار من الجذر إلى قمة معينة.
يمكن استخدام الشجرة لتمثيل الهياكل الهرمية مثل نظام الملفات أو الهياكل التنظيمية للشركة أو أشجار العائلة.
في علوم الكمبيوتر ، هناك العديد من الخوارزميات المتعلقة بالأشجار ، مثل اجتياز الأشجار (للأمام ، والعكس ، والمتناظر) ، وإدخال الرأس وحذفه ، والبحث عن الأشجار ، وغيرها الكثير.
كرسم بياني ثنائي
الرسم البياني الثنائي هو رسم بياني يمكن تقسيم رؤوسه إلى مجموعتين منفصلتين ، بحيث تنتقل جميع الحواف فقط بين رؤوس هاتين المجموعتين.
لإثبات أن الشجرة عبارة عن رسم بياني ثنائي ، يمكنك استخدام خوارزمية تلوين قمة الرأس.
الخطوة 1: نختار أي قمة من الشجرة ونضعها في المجموعة أ.
الخطوة 2: بعد ذلك ، انتقل إلى القمم المجاورة لهذا الرأس ووضعها في المجموعة ب.
الخطوة 3: كرر الخطوة 2 لجميع رؤوس المجموعة ب حتى يتم وضع جميع الرؤوس في المجموعة أ أو ب.
إذا ، بعد الانتهاء من هذه الخوارزمية ، تربط كل حافة رؤوسا من مجموعات مختلفة (أ و ب) ، فإن الشجرة عبارة عن رسم بياني ثنائي.
من المهم ملاحظة أنه ليست كل الأشجار عبارة عن رسوم بيانية ثنائية. إذا كانت الشجرة تحتوي على دورات بعدد فردي من الرؤوس ، فهي ليست رسما بيانيا ثنائي الأجزاء.
الإثبات والتفسير
لإثبات أنه يمكن تمثيل الرسم البياني الثنائي على شكل شجرة ، نحتاج إلى مراعاة الموقف التالي. لنفترض أن لدينا رسما بيانيا ثنائي الأجزاء نريد تمثيله كشجرة. دعونا ننظر في أقصى مطابقة لها.
المطابقة القصوى هي مجموعة من حواف الرسم البياني حيث يتم توصيل كل رأس من فص واحد بحافة برأس واحد فقط من فص آخر ، ولا يمكن زيادة مجموعة الحواف ، أي تتم إضافة حافة للحفاظ على حالة الحد الأقصى.
إذا كان هناك تطابق كامل في رسم بياني ثنائي معين-بحيث يكون كل رأس من الرسم البياني متصلا برأس واحد فقط من الفص الآخر ، فهذا يعني أنه يمكننا تمثيل الرسم البياني على أنه شجرة ذات مستويين.
دعونا نتخيل كل رأس من الفص الأول كرأس للمستوى الأول للشجرة ، وكل رأس من الفص الثاني كرأس للمستوى الثاني للشجرة. ستكون الحواف من الحد الأقصى للمطابقة حواف الشجرة التي تربط رؤوس المستويين الأول والثاني.
يمكن إثبات ذلك من خلال إظهار أن مثل هذا التمثيل سوف يلبي جميع متطلبات الشجرة:
- لا توجد دورات في الشجرة: بحكم تعريف الشجرة ، كل رأس له والد واحد فقط.
- يوجد جذر واحد بالضبط في الشجرة: قمة من المستوى الأول ليس لها آباء.
- كل قمة من الشجرة ليس لديها أكثر من طفلين: من خلال تعريف الرسم البياني الثنائي ، يتم توصيل كل رأس من الفص الأول بحافة برأس واحد فقط من الفص الثاني.
وهكذا ، أثبتنا أنه يمكن تمثيل الرسم البياني الثنائي كشجرة. يمكن استخدام هذا التمثيل لحل المشكلات المختلفة المتعلقة بالرسوم البيانية ثنائية الأجزاء ، مثل إيجاد الحد الأقصى للمطابقة أو إيجاد الحد الأدنى لغطاء الرأس.
هيكل وخصائص
الشجرة هي شكل خاص من الرسم البياني حيث يكون لكل رأس رأس أصل واحد فقط ، باستثناء رأس الجذر ، الذي ليس له أصل.
الخصائص الرئيسية للشجرة:
- الجذر: هذا هو رأس الشجرة التي ليس لها آباء وهي نقطة البداية لعبور الشجرة.
- الأضلاع: هذه هي الروابط بين رؤوس الشجرة. تربط كل حافة رأس أحد الوالدين بأحد رؤوسها الفرعية.
- الأوراق: هذه هي رؤوس الشجرة التي ليس لها رؤوس أطفال.
- المستوى: هذا هو عمق الرأس في الشجرة. يحتوي الجذر على المستوى 0 ، ورؤوسه الفرعية لها المستوى 1 ، وهكذا.
- الارتفاع: هذا هو الحد الأقصى لعدد المستويات في الشجرة. إذا كانت الشجرة تتكون من قمة واحدة ، فإن ارتفاعها هو 0.
- الشجرة الفرعية: هذا هو الجزء من الشجرة الذي يشمل الرأس وجميع أحفاده.
يمكن تمثيل الشجرة كجدول مع عمودين. يشير العمود الأول إلى قمة الشجرة ، ويشير العمود الثاني إلى رأسها الفرعي أو قائمة الرؤوس الفرعية ، إذا كان هناك أكثر من واحد.
| أعلى | قمة رأس الطفل (أو قائمة رؤوس الأطفال) |
|---|---|
| الجذر | قمة الطفل 1 ، قمة الطفل 2, … |
| قمة الطفل 1 | ... |
| قمة الطفل 2 | … |
يمكن أن تكون بنية البيانات هذه مفيدة لتنظيم المعلومات وتنفيذ عمليات معينة على الشجرة ، مثل البحث عن الرؤوس وإدراجها وحذفها.
كنموذج بيانات
، الشجرة هي واحدة من أكثر نماذج البيانات شيوعا وفائدة في علوم الكمبيوتر. إنه رسم بياني تحتوي فيه كل عقدة على والد واحد على الأكثر ويمكن أن تحتوي على عدة عقد فرعية.
يمكن استخدام الشجرة لتمثيل هياكل البيانات المختلفة، مثل:
- التسلسلات الهرمية، مثل الهيكل التنظيمي للشركة أو شجرة العائلة;
- هياكل البيانات مثل أشجار البحث الثنائية أو أكوام;
- أشجار بناء الجملة المجردة المستخدمة في لغات الكمبيوتر والمجمعين لتمثيل البنية النحوية للبرامج;
- أنظمة الملفات حيث كل مجلد هو عقدة شجرة والملفات هي العقد التابعة لها.
واحدة من أكثر العمليات شيوعا مع الشجرة هي اجتياز الأشجار. هناك طرق مختلفة لاجتياز الشجرة ، مثل العبور الأمامي (اجتياز الطلب المسبق) ، والاجتياز المتماثل (اجتياز الترتيب) والاجتياز العكسي (اجتياز ما بعد الطلب). تسمح لك كل طريقة من هذه الطرق بالوصول إلى جميع عقد الشجرة عن طريق إجراء عمليات معينة على كل عقدة.
تستخدم الأشجار أيضا بنشاط في خوارزميات البحث عن البيانات وفرزها. على سبيل المثال ، تتيح لك أشجار البحث الثنائية العثور بكفاءة على العناصر في مجموعة بيانات مرتبة ، وتستخدم أكوام في فرز الخوارزميات والبحث ذي الأولوية.
| مزايا الأشجار: | عيوب الأشجار: |
|---|---|
| الوصول السريع إلى البيانات باستخدام وقت تنفيذ العملية اللوغاريتمية; | عدد محدود من العقد الفرعية لكل عقدة ، والتي يمكن أن تكون غير مريحة في بعض الحالات; |
| المرونة والتنوع في الاستخدام لأنواع مختلفة من البيانات والهياكل; | تعقيد عمليات إعداد وتغيير هيكل الشجرة; |
| سهولة التنفيذ والاستخدام; | المشاكل المحتملة لتحقيق التوازن وكفاءة الشجرة في بعض الحالات. |
بشكل عام ، تعتبر الشجرة أداة قوية لتمثيل ومعالجة البيانات في علوم الكمبيوتر. يسمح لك بالتنظيم والعمل بكفاءة مع هياكل البيانات الهرمية والخطية ، مما يوفر أداء عاليا ومرونة في الاستخدام.
التطبيق في علوم الكمبيوتر
تعتبر الأشجار كرسوم بيانية ثنائية واحدة من هياكل البيانات الرئيسية في علوم الكمبيوتر وتستخدم على نطاق واسع في مختلف المجالات.
في خوارزميات البحث ، على سبيل المثال ، تستخدم الأشجار لتنظيم البيانات وتخزينها بكفاءة. تسمح لك أشجار البحث بإجراء عمليات الإدراج والحذف والبحث عن العناصر في وقت يتناسب مع لوغاريتم عدد العناصر ، مما يجعلها فعالة للغاية بالنسبة لكميات كبيرة من البيانات.
تستخدم الأشجار أيضا في خوارزميات الفرز مثل فرز الدمج أو الفرز السريع. تستخدم هذه الخوارزميات الأشجار لفصل البيانات ودمجها ، مما يسمح بوقت تنفيذ فرز فعال.
يمكن أيضا استخدام الأشجار لنمذجة وتحليل الأنظمة المختلفة. على سبيل المثال ، تستخدم الأشجار في علم الأنساب لتمثيل الروابط الأسرية والأنساب. يتم استخدامها أيضا في هياكل الشبكة ، حيث تمثل العقد الأجهزة أو مكونات الشبكة ، وتمثل الحواف الاتصالات بينها.
بالإضافة إلى ذلك ، يتم استخدام الأشجار في العديد من خوارزميات التحسين وتحديد المسار ، مثل خوارزمية ديكسترا أو خوارزمية أ*. في هذه الخوارزميات ، تستخدم الأشجار لتنظيم وتمثيل المسارات أو الحالات المحتملة للنظام ، وكذلك لتحديد المسارات أو الحلول المثلى.
بشكل عام ، تلعب الأشجار كرسوم بيانية ثنائية دورا مهما في علوم الكمبيوتر وتستخدم في العديد من المجالات التي تتطلب تنظيم ومعالجة البيانات بكفاءة أو نمذجة النظام أو التحسين والبحث.
تصنيف الأشجار
يمكن تصنيف الأشجار وفقا لمعايير مختلفة. فيما يلي بعض الأنواع الأساسية من الأشجار:
الأشجار الثنائية: كل عقدة ليس لها أكثر من نسلين. يمكن تصنيف الأشجار الثنائية بشكل أكبر إلى أشجار ثنائية كاملة ، حيث يكون لجميع العقد باستثناء الأوراق نسلان ، وأشجار ثنائية متوازنة ، حيث لا يتجاوز فرق الارتفاع بين الشجرة الفرعية اليسرى واليمنى واحدا.
أشجار البحث الثنائية: تحتوي كل عقدة على روابط إلى نسلين ، حيث تكون جميع القيم في الشجرة الفرعية اليسرى أقل من القيمة في هذه العقدة ، وتكون جميع القيم في الشجرة الفرعية اليمنى أكبر من القيمة في هذه العقدة.
الأشجار الحمراء السوداء: الأشجار الثنائية التي تحتوي فيها كل عقدة على خاصية لون إضافية (أحمر أو أسود). يتم الحفاظ على ألوان العقدة بطريقة تتحقق فيها الخصائص الأساسية للأشجار ذات اللون الأحمر والأسود ، مثل كل مسار من الجذر إلى الورقة يحتوي على نفس عدد العقد السوداء.
أفل الأشجار: الأشجار الثنائية المتوازنة التي لا يتجاوز فيها فرق الارتفاع بين الشجرة الفرعية اليمنى واليسرى لكل عقدة واحدة.
ب-الأشجار: الأشجار المصممة خصيصا لتخزين واسترجاع البيانات بكفاءة على الأجهزة الخارجية. ب-الأشجار لديها درجة كبيرة ودعم عقدة التوازن والانقسام.
كل نوع من الأشجار له خصائصه وتطبيقاته الخاصة في مختلف المجالات. تساعد دراسة وفهم هذه التصنيفات على فهم بنية الأشجار بشكل أفضل واختيار النوع الأنسب لمهمة معينة.
خوارزميات اجتياز الأشجار
في هذا القسم ، سنلقي نظرة على خوارزميات اجتياز الشجرة الأساسية: تجاوز في العمق وتجاوز في العرض.
الزحف العميق
يسمح لك الزحف العميق بزيارة جميع رؤوس الشجرة ، بدءا من قمة معينة والانتقال إلى أسفل كل فرع حتى الوصول إلى القمة النهائية. علاوة على ذلك ، عند العبور في العمق ، هناك عودة إلى الرأس السابق واستمرار العبور في عمق القمم المجاورة.
هناك عدة خيارات للذهاب في العمق:
- اجتياز مباشر (طلب مسبق) - بهذه الطريقة ، تتم معالجة الرأس الحالي أولا ، ثم يتم اجتياز الأشجار الفرعية اليمنى واليسرى.
- اجتياز متماثل (بالترتيب) - بهذه الطريقة ، يتم اجتياز الشجرة الفرعية اليسرى أولا ، ثم تتم معالجة الرأس الحالي ، وأخيرا يتم اجتياز الشجرة الفرعية اليمنى.
- اجتياز عكسي (بعد الطلب) - بهذه الطريقة ، يتم اجتياز الأشجار الفرعية اليمنى واليسرى أولا ، ثم تتم معالجة الرأس الحالي.
اجتياز العرض
اتساع-اجتياز الأول هو خوارزمية اجتياز شجرة شعبية أخرى. باستخدام طريقة العبور هذه ، تتم زيارة رؤوس الشجرة بمستويات ، بدءا من الجذر والانتقال من اليسار إلى اليمين.
تستخدم خوارزمية اجتياز العرض الأول قائمة انتظار (فيفو) لتخزين القمم. تبدأ عملية الزحف بإضافة رأس الجذر إلى قائمة الانتظار. ثم ، في كل خطوة ، يتم استخراج قمة الرأس من قائمة الانتظار ، ويتم إضافة جميع أحفادها غير المرغوب فيها إلى قائمة الانتظار. تستمر هذه العملية طالما كانت هناك رؤوس غير مرغوب فيها في قائمة الانتظار.
يسمح لك اجتياز العرض الأول بزيارة جميع رؤوس الشجرة حسب المستويات ويمكن أن يكون مفيدا ، على سبيل المثال ، للعثور على أقصر طريق بين رأسين.
عند البرمجة ، يمكن تنفيذ خوارزميات اجتياز الأشجار باستخدام العودية أو باستخدام الأكوام وقوائم الانتظار.
سؤال وجواب
كيف يمكن تمثيل الشجرة كرسم بياني ثنائي?
يمكن استخدام الخوارزمية التالية لتمثيل الشجرة كرسم بياني ثنائي. دعونا نبدأ مع قمة التعسفي من الشجرة ووضع علامة عليه مع الفص الأول (دعونا نسميها "أ"). ثم نضع علامة على جميع الرؤوس المجاورة لهذا الرأس بكسر آخر (دعنا نسميها "ب"). بعد ذلك ، نحتفل بجميع القمم المجاورة للرؤوس من الفص الثاني للفص الأول وما إلى ذلك. بعد ذلك ، لكل قمة في الشجرة ، يمكنك تحديد أي حصة تنتمي إليها. إذا كان الرأس ينتمي إلى الفص الأول ، فإنه متصل بحافة فقط برؤوس الفص الثاني ، والعكس صحيح. وبالتالي ، ستكون الشجرة رسما بيانيا ثنائي الأجزاء.
لماذا يمكن تمثيل الشجرة كرسم بياني ثنائي?
الشجرة هي حالة خاصة للرسم البياني لا توجد فيها دورات. بحكم التعريف ، الرسم البياني الثنائي هو رسم بياني يمكن تقسيم رؤوسه إلى فصين بحيث تربط الحواف فقط رؤوس الفصوص المختلفة. لا توجد دورات في الشجرة ، لذلك يمكن تقسيم رؤوسها إلى فصين بحيث تربط جميع الحواف الرؤوس من فصوص مختلفة. وبالتالي،يمكن تمثيل الشجرة كرسم بياني ثنائي.
ما هي ميزة تمثيل شجرة كرسم بياني ثنائي?
يعد تمثيل الشجرة كرسم بياني ثنائي مفيدا في حل المشكلات المختلفة. على سبيل المثال ، يمكن استخدام الرسوم البيانية ثنائية الأجزاء بشكل ملائم لحل مشاكل تغطية الرؤوس أو الحواف بأقل عدد ، أو مشاكل المطابقة القصوى ، أو إيجاد أصغر مسار بين رؤوس الكسور المختلفة. يمكن أن يساعد تمثيل الشجرة كرسم بياني ثنائي في تبسيط الخوارزميات والحصول على حلول فعالة لهذه المشكلات.
ما هي العلاقة بين الرسوم البيانية الثنائية والأشجار?
الرسوم البيانية والأشجار الثنائية هي هياكل رياضية مختلفة. ومع ذلك ، فإن الشجرة هي حالة خاصة للرسم البياني الثنائي. إذا أخذنا أي شجرة وقمنا بتمثيلها على شكل رسم بياني ثنائي ، فسيكون الرسم البياني الناتج ثنائي. من ناحية أخرى ، ليست كل الرسوم البيانية ثنائية الأجزاء عبارة عن أشجار. ومع ذلك ، تساعد الرسوم البيانية الثنائية في حل المشكلات المتعلقة بالأشجار بسبب هيكلها المحدد.