تتكون بنية البيانات غير الخطية من مجموعة من العناصر التي يتم توزيعها على مستوى ما يعني عدم وجود مثل هذا التسلسل بين العناصر كما هو موجود في بنية بيانات خطية.
رسم بياني للمقارنة
| أساس للمقارنة | شجرة | رسم بياني |
|---|---|---|
| مسار | واحد فقط بين القمم اثنين. | أكثر من مسار واحد مسموح به. |
| عقدة الجذر | لديه عقدة جذر واحدة بالضبط. | لا يحتوي الرسم البياني على عقدة جذر. |
| الحلقات | لا يسمح الحلقات. | الرسم البياني يمكن أن يكون الحلقات. |
| تعقيد | أقل تعقيدا | أكثر تعقيدا نسبيا |
| تقنيات العبور | طلب مسبق ، حسب الطلب وبعده. | بحث أول بحث وعمق أول البحث. |
| عدد الحواف | n-1 (حيث n هو عدد العقد) | غير معرف |
| نوع النموذج | الهرمية | شبكة الاتصال |
تعريف الشجرة
الشجرة عبارة عن مجموعة منتهية من عناصر البيانات تسمى عادةً بالعقد. كما ذكر أعلاه ، فإن الشجرة عبارة عن هيكل بيانات غير خطي يرتب عناصر البيانات بترتيب مفروز. يتم استخدامه لإظهار بنية هرمية بين عناصر البيانات المختلفة وينظم البيانات في الفروع التي تربط المعلومات. تؤدي إضافة حافة جديدة في الشجرة إلى تشكيل الحلقة أو الدائرة.
هناك عدة أنواع من الأشجار مثل شجرة ثنائية ، شجرة بحث ثنائية ، شجرة AVL ، شجرة ثنائية مترابطة ، B-tree ، إلخ. ضغط البيانات ، تخزين الملفات ، التلاعب بالأشكال الحسابية وأشجار اللعبة هي بعض تطبيقات الشجرة هيكل البيانات.
خصائص الشجرة:
- هناك عقدة محددة في الجزء العلوي من الشجرة المعروفة باسم جذر الشجرة.
- يتم تقسيم العناصر المتبقية البيانات إلى مجموعات فرعية منفصلة الرجوع إلى كـ subtree.
- يتم توسيع الشجرة في الارتفاع نحو القاع.
- يجب أن تكون شجرة متصلة مما يعني أنه يجب أن يكون هناك مسار من جذر واحد إلى جميع العقد الأخرى.
- لا يحتوي على أي حلقات.
- تحتوي الشجرة على حواف n-1.
هناك العديد من المصطلحات المرتبطة بالأشجار مثل عقدة طرفية ، حافة ، مستوى ، درجة ، عمق ، غابة ، إلخ. ومن بين هذه المصطلحات ، بعضها موضح أدناه.
- الحافة - خط يربط بين نقطتين.
- المستوى - يتم تقسيم الشجرة إلى مستويات بحيث تكون العقدة الجذرية عند المستوى 0. ثم ، يكون أطفالها المباشرين في المستوى 1 ، ويكون أطفالهم المباشرين في المستوى 2 وهكذا حتى إلى طرف المحطة الطرفية أو عقدة الورقة.
- الدرجة - هو عدد الألواح الفرعية لعقدة في شجرة معينة.
- العمق - هو أقصى مستوى لأي عقدة في شجرة معينة ويعرف أيضًا بالارتفاع .
- عقدة طرفية - عقدة المستوى الأعلى هي عقدة طرفية بينما تُعرف العقد الأخرى باستثناء الطرفية والعقد الجذرية باسم العقد غير الطرفية.
تعريف الرسم البياني
الرسم البياني هو أيضًا بنية بيانات غير خطية رياضية يمكن أن تمثل أنواعًا مختلفة من البنية الفيزيائية. يتكون من مجموعة من الرؤوس (أو العقد) ومجموعة من الحواف التي تربط بين القمتين. يتم تمثيل الرؤوس على الرسم البياني كنقطة أو دائرة وتظهر الحواف كأقواس أو أجزاء خطية. يتم تمثيل حافة بواسطة E (v، w) حيث v و w هما أزواج القمم. تؤدي إزالة حافة من دائرة أو رسم بياني متصل إلى إنشاء مخطط فرعي يمثل شجرة.
يتم تصنيف الرسوم البيانية إلى فئات مختلفة مثل التوجيهات وغير الموجهة ، والمتصلة ، وغير المتصلة ، وبسيطة ومتعددة الرسم البياني. شبكة الكمبيوتر ، ونظام النقل ، والرسم البياني للشبكة الاجتماعية ، والدوائر الكهربائية وتخطيط المشاريع هي بعض تطبيقات بنية بيانات الرسم البياني. كما يتم استخدامه أيضًا في تقنية الإدارة المسماة PERT (تقييم البرنامج وتقويم المراجعة) و CPM (طريقة المسار الحرج) التي يتم تحليل بنية الرسم البياني بها.
خصائص الرسم البياني:
- يمكن توصيل قمة الرأس في الرسم البياني بأي عدد من الرؤوس الأخرى باستخدام الحواف.
- يمكن أن تكون bidirected أو توجيه حافة.
- يمكن ترجيح الحافة.
في الرسم البياني أيضًا ، نستخدم مصطلحات متنوعة مثل الرؤوس المجاورة ، والمسار ، والدورة ، والدرجة ، والرسم البياني الموصل ، والرسم البياني الكامل ، والرسم البياني المرجح ، وما إلى ذلك. لنفهم بعض هذه العبارات.
- القمم المجاورة - توجد قمة الرأس مجاورة للرأس b إذا كان هناك حافة (a، b) أو (b، a).
- المسار - المسار من قمة الرأس العشوائية هو سلسلة متتالية من الرؤوس.
- دورة - هو مسار حيث القمم الأولى والأخيرة هي نفسها.
- درجة - وهو عدد من حواف الحادث على قمة الرأس.
- الرسم البياني المتصل - إذا كان هناك مسار من قمة رأسية عشوائية إلى أي قمة أخرى ، فإن هذا الرسم البياني يُعرف بالرسم البياني الموصل.
الاختلافات الرئيسية بين شجرة والرسم البياني
- في شجرة يوجد مسار واحد فقط بين أي رأسين بينما يمكن أن يحتوي الرسم البياني على مسارات أحادية الاتجاه وثنائية الاتجاه بين العقد.
- في الشجرة ، توجد عقدة جذر واحدة تمامًا ، ويمكن أن يكون لكل طفل والد واحد فقط. مقابل ، في الرسم البياني ، لا يوجد مفهوم عقدة الجذر.
- لا يمكن أن تحتوي الشجرة على حلقات وحلقات ذاتية في حين أن الرسم البياني يمكن أن يكون به حلقات وحلقات ذاتية.
- الرسوم البيانية هي أكثر تعقيدا لأنها يمكن أن يكون لها الحلقات والحلقات الذاتية. في المقابل ، تعتبر الأشجار بسيطة مقارنة بالرسم البياني.
- يتم عبور الشجرة باستخدام أساليب الطلب المسبق والنظام والتقريري. من ناحية أخرى ، بالنسبة إلى اجتياز الرسم البياني ، نستخدم BFS (Breadth First Search) و DFS (Depth First Search).
- يمكن أن تحتوي الشجرة على n-1 حواف. على العكس ، في الرسم البياني ، لا يوجد عدد محدد مسبقًا من الحواف ، ويعتمد ذلك على الرسم البياني.
- تحتوي الشجرة على هيكل هرمي بينما يحتوي الرسم البياني على نموذج شبكة.
استنتاج
الرسم البياني والشجرة هي بنية البيانات غير الخطية التي تستخدم لحل مختلف المشاكل المعقدة. الرسم البياني عبارة عن مجموعة من الرؤوس والحواف حيث تربط الحافة زوجًا من الرؤوس بينما تعتبر الشجرة رسمًا بيانيًا متصلاً بالحد الأدنى ويجب أن يكون متصلاً وخاليًا من الحلقات.
