شرح 4 أنواع من الأشجار في بنية البيانات: الخصائص والتطبيقات

ما هي الشجرة في بنية البيانات؟

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

بعض المصطلحات المرتبطة بالأشجار في بنية البيانات هي:

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

أنواع الأشجار

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

الشجرة الثنائية هي نوع من بنية بيانات الشجرة حيث تحتوي كل عقدة رئيسية على عقدتين فرعيتين بحد أقصى. كما يوحي الاسم ، يعني الثنائي اثنين ، وبالتالي ، يمكن أن تحتوي كل عقدة على 0 أو 1 أو 2. يظهر هيكل بيانات الشجرة الثنائية في الشكل 1. تحتوي العقدة 1 في الشجرة على مؤشرين ، واحد لكل عقدة فرعية. تحتوي العقدة 2 مرة أخرى على مؤشرين لكل من العقدتين الفرعيتين. في حين أن العقدة 3 و 5 و 6 هي عقد طرفية ، وبالتالي ، تحتوي على مؤشرات فارغة في كلا الجزأين الأيمن والأيسر.

الشكل 1: تمثيل لشجرة ثنائية ( https://www.javatpoint.com/binary-tree ).

خصائص الشجرة الثنائية

• الحد الأقصى لعدد العقد في كل مستوى من I هو 2 i .
• ارتفاع الشجرة في الشكل 1 هو 3 مما يعني أن الحد الأقصى لعدد العقد سيكون (1 + 2 + 4 + 8) = 15.

• عند ارتفاع h ، يكون أقصى عدد ممكن من العقد هو (20 + 21 + 22 + ... .2h) = 2h + 1 -1.

• عند الارتفاع h ، يكون الحد الأدنى لعدد العقد الممكنة مساويًا لـ h + 1.

• سيمثل الحد الأدنى لعدد العقد شجرة ذات أقصى ارتفاع والعكس صحيح.

حتى الأشجار الثنائية يمكن تقسيمها إلى الأنواع التالية من الأشجار:

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

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

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

• تحتوي كل عقدة على عقدتين فرعيتين بحد أقصى.
• يمكن استخدامه للبحث عن عنصر في الوقت 0 (log (n)) ومن ثم يُعرف باسم شجرة البحث.

الشكل: مثال على شجرة بحث ثنائية ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

خصائص شجرة البحث الثنائية هي:

• يجب أن تكون القيمة في جميع عقد الشجرة الفرعية اليسرى أقل من القيمة الموجودة في عقدة الجذر.
• يجب أن تكون القيمة في جميع عقد الشجرة الفرعية اليمنى أكبر من القيمة الموجودة في عقدة الجذر.

3. شجرة AVL

أشجار AVL هي أنواع أو متغيرات الشجرة الثنائية. وهو يتألف من خصائص من كل من الثنائي وكذلك شجرة البحث الثنائية. اخترع Adelson Velsky Lindas هذه الأشجار ذاتية التوازن مما يعني أن ارتفاع الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى متوازنة. يتم قياس هذا الرصيد من حيث عامل التوازن.

عامل التوازن:

• إنه الفرق بين الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى.
• يجب أن تكون قيمة عامل التوازن 0 ، -1 ، أو 1. لذلك ، يجب أن تتكون كل عقدة في شجرة AVL من قيمة عامل موازنة ، أي 0 ، -1 ، أو 1.
• عامل التوازن = (ارتفاع الشجرة الفرعية اليسرى - ارتفاع الشجرة الفرعية اليمنى)
• يُقال أن شجرة AVL هي شجرة متوازنة إذا كان عامل التوازن لكل عقدة بين -1 إلى 1.

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

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

4. B- شجرة

B Tree هو شكل أكثر عمومية لشجرة بحث ثنائية. تُعرف أيضًا باسم شجرة الطريق متوازنة الارتفاع ، حيث م هو ترتيب الشجرة. يمكن أن تحتوي كل عقدة في الشجرة على أكثر من مفتاح واحد وأكثر من عقدتين فرعيتين. في حالة الشجرة الثنائية ، قد لا تكون العقد الورقية على نفس المستوى. ومع ذلك ، في حالة B Tree ، يجب أن تكون جميع العقد الطرفية في نفس المستوى.

خصائص شجرة ب:

• يتم تخزين المفاتيح بترتيب تصاعدي لكل عقدة x.
• توجد القيمة المنطقية "x.leaf" في كل عقدة ، وهذا صحيح إذا كانت x ورقة.
• يجب أن تحتوي العقد الداخلية على مفاتيح "n-1" كحد أقصى ، حيث يمثل n ترتيب الشجرة. يجب أن تحتوي أيضًا على مؤشر لكل طفل.
• ستحتوي جميع العقد على n على الأكثر من الأطفال وعلى الأقل n / 2 الأطفال ، باستثناء عقدة الجذر.
• العقد الورقية للشجرة لها نفس العمق.
• سيكون للعقدة الجذرية مفتاح واحد على الأقل وطفلين على الأقل.
• إذا كانت n ≥ 1 ، فعندئذٍ لأي شجرة B ذات مفتاح n بارتفاع h والحد الأدنى للدرجة t ≥ 2 ، h ≥ logt (n + 1) / 2.

التطبيقات

• يمكن تطبيق شجرة البحث الثنائي للبحث عن عنصر في مجموعة من العناصر.
• يتم استخدام أشجار الكومة لفرز الكومة.
• تستخدم أجهزة التوجيه الحديثة نوعًا من الشجرة يسمى "محاولات" لتخزين معلومات التوجيه.
• يتم استخدام الأشجار B و T-Trees في الغالب بواسطة قواعد البيانات الشائعة لتخزين بياناتها.
• يتم استخدام شجرة النحو من قبل المترجمين للتحقق من صحة بناء الجملة لكل برنامج مكتوب.

خاتمة

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

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

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

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