الأشجار في بنية البيانات: 8 أنواع من الأشجار يجب أن يعرفها كل عالم بيانات

مقدمة

في مجال الحوسبة ، تشير هياكل البيانات إلى نمط ترتيب البيانات على القرص ، مما يتيح تخزين وعرض مناسبين. إنها تتعلق بمجال علم البيانات ، والذي من المتوقع أن يكون اختيارًا مهنيًا مربحًا في عام 2021. استنادًا إلى التوقعات للسنوات القليلة المقبلة ، ستمهد نماذج التعلم العميق واسعة النطاق والأجهزة الذكية من الجيل التالي مستقبل هذا القطاع.

وبالتالي ، فإن الحصول على المعرفة بهياكل البيانات سيكون ضروريًا لإيجاد مهنة مناسبة وسط التقدم التكنولوجي. وفقًا لتنبؤات صناعة علوم البيانات لعام 2021 ، ستوظف الولايات المتحدة والهند ما يقرب من 50000 عالم بيانات و 300000 محلل بيانات ضمن أكثر من 250000 شركة. [1]

يتم تطبيق هياكل البيانات لتصميم مسارات لتخصيص وإدارة واسترجاع المعلومات. تعتبر هياكل البيانات ضرورية بشكل خاص لصياغة وتحسين كفاءة البيانات المعالجة الإجمالية. يديرون البيانات من خلال تجميعها وتنظيمها لتسهيل تبادل المعلومات بشكل فعال.

الأشجار في هياكل البيانات

"الأشجار" هي نوع من أنواع بيانات ADT (أنواع البيانات المجردة) ، والتي تتبع نمطًا هرميًا لتخصيص البيانات الخاصة بها. في الأساس ، الشجرة عبارة عن مجموعة من العقد المتعددة المتصلة عبر الحواف. تشكل هذه "الأشجار" تصميمًا لهيكل البيانات يشبه الشجرة ، حيث تؤدي عقدة "الجذر" إلى العقد "الأصل" ، والتي تؤدي في النهاية إلى عقد "فرعية". يتم إجراء التوصيلات بخطوط تعرف باسم "الحواف".

العقد "الورقية" هي نقاط نهاية مع عدم وجود عقد فرعية أخرى تنشأ منها. تلعب الأشجار في هياكل البيانات دورًا حيويًا نظرًا للطبيعة غير الخطية لترتيبها. يتيح ذلك وقت استجابة أسرع أثناء البحث ، إلى جانب الراحة خلال مراحل التصميم.

أنواع الأشجار في بنية البيانات

يتم شرح الأنواع المختلفة من الأشجار في هياكل البيانات بالتفصيل أدناه:

1. الشجرة العامة

تتميز الشجرة العامة بعدم وجود أي مواصفات أو قيود على عدد الأطفال الذين يمكن أن تحتويهم العقدة. يمكن تصنيف أي شجرة ذات هيكل هرمي كشجرة عامة. يمكن أن تحتوي العقدة على عدة توابع ، ويمكن أن يكون هناك أي نوع من التوليفات لاتجاه الشجرة. يمكن أن تكون العقد من أي درجة ، من 0 إلى n.

فيما يلي مثال كلاسيكي لشجرة عامة في بنية البيانات ، حيث يمثل الرقم "2" في الجزء العلوي العقدة الجذرية.

مصدر

2. شجرة ثنائية

كما هو محدد بواسطة كلمة "ثنائي" ، والتي تعني رقمين ، تتكون الشجرة الثنائية من عقد يمكن أن تحتوي على عقدتين فرعيتين. يمكن أن تحتوي أي عقدة في الشجرة الثنائية على 0 أو 1 أو 2 على الأكثر. الأشجار الثنائية في هياكل البيانات هي أدوات ADT عالية الأداء ويمكن تقسيمها إلى عدة أنواع. يتم استخدامها بشكل أساسي في هياكل البيانات لغرضين:

1. للوصول إلى العقد وتمييزها ، كما هو مذكور في Binary Search Trees.
2. لتمثيل البيانات من خلال هيكل متشعب.

فيما يلي رسم تخطيطي أساسي لشجرة ثنائية في بنية بيانات:

مصدر

3. شجرة البحث الثنائية

شجرة البحث الثنائية (BST) هي نوع فرعي فريد من الأشجار الثنائية التي يتم ترتيبها بطريقة تسهل البحث / البحث بشكل أسرع أو إضافة / إزالة البيانات. يتم تعريف BST من خلال تمثيل العقد بناءً على ثلاثة حقول: البيانات ، والتابعة الأيسر ، والفرع الأيمن. العوامل الحاكمة لـ BST هي:

1. يجب أن تحتوي كل عقدة على الجانب الأيسر (الطفل الأيسر) على قيمة أقل من العقدة الأصلية.
2. يجب أن تحتوي كل عقدة على الجانب الأيمن (الطفل الأيمن) على قيمة أعلى من العقدة الأصلية.

مثل هذا الترتيب يقلل من أوقات البحث إلى نصف البحث الخطي ، كما هو موجود في المصفوفة. وبالتالي ، فإن أشجار البحث الثنائية في هياكل البيانات قابلة للتطبيق على نطاق واسع للبحث والفرز مقارنةً بـ ADTs الأخرى.

مصدر

على الرغم من أن كلا من BTs و BSTs عبارة عن أشجار في هياكل البيانات ، لا تربكك التشابه في أسمائها. اكتشف الفرق بين الشجرة الثنائية وشجرة البحث الثنائية بالتفصيل في upGrad.

4. شجرة AVL

تشتق شجرة AVL اسمها من مخترعيها: Adelson-Velsky و Landis. تتميز شجرة AVL بطابع ذاتي التوازن. يتم تحديد ارتفاعات شجرتين فرعيتين من العقد الجذرية الخاصة بها بأقل من اثنين. عندما يزيد فرق الارتفاع عن 1 ، تتم إعادة موازنة العقد الفرعية.

تتميز أشجار AVL بارتفاع متوازن ، وتحدث إعادة التوازن هذه من خلال دورات فردية أو مزدوجة. عامل الموازنة هو الفرق بين ارتفاعات الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى ، والقيم هي -1 و 0 و 1.

5. شجرة حمراء سوداء

هذا النوع يشبه أشجار AVL لأن الأشجار السوداء الحمراء متوازنة الارتفاع أيضًا. ما يفصل بينهما هو أنه لا يتطلب أكثر من دورتين لتحقيق التوازن بينهما. تحتوي على جزء إضافي يحدد اللون الأحمر أو الأسود للعقدة ، مما يضمن توازن الأشجار أثناء عمليات الحذف والإدخال. يتم أيضًا إعادة طلاء الترميز باللون الأحمر والأسود أثناء التغييرات ولكن بدون تكلفة إضافية للذاكرة تقريبًا.

6. شجرة سبلاي

نوع فرعي آخر من شجرة البحث الثنائية ، شجرة الفاصل ، له خاصية فريدة لإجراء عمليات الدوران لضبط العقدة الأخيرة. يتم ترتيب العقدة التي تم الوصول إليها مؤخرًا كعقدة جذر عن طريق إجراء تدوير. إنها شجرة متوازنة ، لكنها ليست شجرة متوازنة الطول.

يتم تنفيذ عملية "الرش" بعد البحث الأولي عن الشجرة الثنائية ، حيث يتم إجراء دورات الأشجار بطريقة معينة. بعد كل عملية ، يتم تدوير الشجرة لتوازن نفسها ، ويتم ترتيب العنصر الذي تم البحث عنه في الأعلى كعقدة جذر.

7. خنزير

"Treaps" في هياكل البيانات عبارة عن مزيج من الأشجار والأكوام. في BSTs ، يجب أن تكون قيمة الطفل الأيسر أقل من عقدة الجذر ، ويجب أن تكون قيمة الطفل الأيمن أعلى. في بنية بيانات كومة الذاكرة المؤقتة ، تحتوي العقدة الجذرية على أقل قيمة ، وتحتوي العقد الفرعية (اليسرى واليمنى) على قيم أكبر.

وبالتالي ، فإن treap يحمل قيمة في شكل مفتاح (يشبه BSTs) وأولوية (مثل الأكوام). يتم إدراج العقد ذات الأولوية القصوى أولاً في شجرة البحث الثنائية بطريقة تجعل الأرقام ذات الأولوية أرقامًا عشوائية مستقلة. يحتفظون بمجموعة ديناميكية من المفاتيح المرتبة ويسمحون بالبحث الثنائي داخل مفاتيحهم.

8. شجرة ب

كنوع من الشجرة ذاتية التوازن في هياكل البيانات ، يقوم B-Tree بفرز البيانات للسماح بالبحث والوصول المتسلسل والحذف والإدخالات في الوقت اللوغاريتمي. على عكس الشجرة الثنائية ، تسمح الشجرة B لعقدها بأن يكون لها أكثر من طفلين. وهي متوافقة مع قواعد البيانات وأنظمة الملفات التي تقرأ وتكتب كتل أكبر من البيانات.

تُستخدم شجرة B في هياكل البيانات لأنظمة التخزين الأكبر ، مثل الأقراص. جميع الأوراق لا تحمل أي معلومات ، وتظهر في نفس المستوى. يمكن أن تحتوي العقد الداخلية للشجرة B على حجم متغير من العقد الفرعية المرتبطة بنطاق.

هذه هي الأشجار في هياكل البيانات ، والتي يتم تنفيذها من قبل المبرمجين الذين يصممون تدفق البيانات. يعد تعلم خصائصها الفريدة وتطبيقاتها أمرًا ضروريًا لرحلتك لتصبح عالم بيانات. هناك طريقة أخرى لتحسين مهاراتك وهي التدرب من خلال العديد من المشاريع التي تتطلب معرفة الأشجار في هياكل البيانات وأشكال أخرى من ADTs.

لتطبيق معرفتك على مشاريع DS ، تحتوي روابط المدونة التالية على 13 فكرة مثيرة للاهتمام حول مشاريع بنية البيانات وموضوعًا للمبتدئين [2021] .

خاتمة

قد يكون التعرف على مفاهيم مثل الأشجار في بنية البيانات أمرًا صعبًا ، ويحتاج الطامحون في البرمجة إلى توجيه من الخبراء لتثقيف أنفسهم. لمعرفة المزيد حول الأشجار في بنية البيانات ، تحقق من الدورات التدريبية عبر الإنترنت التي تقدمها upGrad . يمكن أن يساعدك برنامج PG التنفيذي في تطوير البرمجيات - التخصص في DevOps مع DevOps من IIIT-B & upGrad في بناء حياتك المهنية كمبرمج.

نظرًا لأن كفاءة هياكل البيانات جزء لا يتجزأ من عملية الترميز ، فيمكن أن تساعد الطالب في أن يصبح مبرمجًا خبيرًا ومطور برامج. لا بد أن يكون المبرمجون وعلماء البيانات مطلوبين للعقود القادمة.

لدينا 500 مليون مستخدم للإنترنت في الهند ، يولدون ويستهلكون كميات كبيرة من البيانات ، الأمر الذي يتطلب توظيف الآلاف من علماء البيانات لتلبية الطلب. [2] يحتاج علماء البيانات هؤلاء إلى التعليم المناسب ، مع الخبرة التكنولوجية ذات الصلة ، للبحث عن عمل في هذا القطاع.

يمكن أن يساعدك برنامج PG التنفيذي في تطوير البرامج - التخصص في تطوير Full Stack ، برعاية upGrad & IIIT-Bangalore ، في تحسين ملفك الشخصي وتأمين فرص عمل أفضل كمبرمج.