شرح أنواع 5 من الأشجار الثنائية [مع الرسوم التوضيحية]

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

لا توجد قيود على بنية بيانات الشجرة العامة على عدد العقد الفرعية التي يمكنها الاحتفاظ بها. ومع ذلك ، ليس هذا هو الحال مع الشجرة الثنائية. ستتعرف هذه المقالة على هيكل بيانات شجرة معين - الشجرة الثنائية وأنواع الشجرة الثنائية .

ما هو هيكل بيانات الشجرة الثنائية؟

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

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

المصطلحات المرتبطة بالأشجار الثنائية وأنواع الأشجار الثنائية

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

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

مكونات الشجرة الثنائية

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

1. عنصر البيانات
2. المؤشر إلى الشجرة الفرعية اليسرى
3. المؤشر إلى الشجرة الفرعية اليمنى

مصدر

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

قراءة: أهم أسئلة Guesstimate وأساليب إعلامية لعلوم البيانات

أنواع الأشجار الثنائية

هناك أنواع مختلفة من الأشجار الثنائية ، ولكل نوع من أنواع الأشجار الثنائية خصائص فريدة. فيما يلي تفاصيل كل نوع من أنواع الأشجار الثنائية :

1. شجرة ثنائية كاملة

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

بمعنى آخر ، الشجرة الثنائية الكاملة هي شجرة ثنائية فريدة حيث يكون لكل عقدة ما عدا العقدة الخارجية طفلان. عندما تحمل طفلًا واحدًا ، لن تكون هذه الشجرة الثنائية شجرة ثنائية كاملة. هنا ، كمية العقد الورقية تساوي عدد العقد الداخلية زائد واحد. المعادلة مثل L = I + 1 ، حيث L هو عدد العقد الورقية ، وأنا هو عدد العقد الداخلية.

هنا هيكل الشجرة الثنائية الكاملة:

2. أكمل شجرة ثنائية

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

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

يُقال أن الشجرة الثنائية "مثالية" إذا كان لجميع العقد الداخلية طفلان فقط ، وكانت كل عقدة خارجية أو ورقية على نفس المستوى أو نفس العمق داخل الشجرة. تحتوي الشجرة الثنائية المثالية التي يبلغ ارتفاعها 'h' على عقدة من ساعتين إلى 1. هذا هو هيكل الشجرة الثنائية المثالية:

4. شجرة ثنائية متوازنة

يُقال أن الشجرة الثنائية "متوازنة" إذا كان ارتفاع الشجرة هو O (logN) ، حيث "N" هو عدد العقد. في الشجرة الثنائية المتوازنة ، يجب أن يختلف ارتفاع الشجرة الفرعية اليمنى واليسرى لكل عقدة بمقدار واحد على الأكثر. شجرة AVL وشجرة الأحمر والأسود هي بعض الأمثلة الشائعة لهيكل البيانات التي يمكن أن تولد شجرة بحث ثنائية متوازنة. فيما يلي مثال على شجرة ثنائية متوازنة:

5. منحط شجرة ثنائية

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

فوائد الشجرة الثنائية

• تكون عملية البحث في الشجرة الثنائية أسرع مقارنة بالأشجار الأخرى
• يكفي اجتيازان فقط لتوفير العناصر بالترتيب الفرز
• من السهل التقاط الحد الأقصى والحد الأدنى من العناصر
• يستخدم اجتياز الرسم البياني أيضًا الأشجار الثنائية
• من الممكن تحويل تعابير مختلفة من postfix والبادئة باستخدام الأشجار الثنائية

اقرأ أيضًا: أشجار القرار في التعلم الآلي: الوظائف والتصنيف والإيجابيات والسلبيات

خاتمة

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

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