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

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

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

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

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

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

العقدة: تحتوي على قيمة بيانات في شجرة ثنائية.

الجذر: العقدة العليا في أي شجرة ثنائية تسمى جذر الشجرة.

الحجم: يشير إلى عدد العقد في الشجرة الثنائية.

العقدة الأصلية: عقدة في شجرة ثنائية مع طفل.

العقدة الفرعية: هي عقدة تنشأ من عقدة أصل تبتعد عن جذر الشجرة الثنائية.

العقدة الداخلية: هي عقدة بها طفل واحد على الأقل في شجرة ثنائية.

العقدة الورقية: هي عقدة ليس لها طفل.إنها بدلاً من ذلك عقدة خارجية.

عمق شجرة العقدة: يتم حسابه في سياق عقدة معينة.يشار إليه على أنه عدد الحواف من عقدة معينة إلى الجذر.

طول المسار الداخلي للشجرة: يشير إلى مجموع مستويات كل عقدة داخلية في شجرة ثنائية.

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

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

الآن دعنا نتحقق من تفاصيل 5أنواع من الشجرة الثنائية.

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

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

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

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

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

فيما يلي خصائص الشجرة الثنائية الكاملة:

• عدد العقد الطرفية يساوي عدد العقد الداخلية + 1. على سبيل المثال ، إذا كان عدد العقد الداخلية 4 ، فإن عدد العقد الطرفية يساوي 5.
• العدد الأقصى للعقد وعدد العقد في الشجرة الثنائية متساويان. يتم تمثيله على أنه 2h + 1 -1.
• الحد الأدنى لعدد العقد في الشجرة الثنائية الكاملة هو 2h-1.
• الحد الأدنى لارتفاع الشجرة الثنائية الكاملة هو log 2 (n + 1) - 1.
• أقصى ارتفاع لشجرة ثنائية كاملة هو h = (n + 1) / 2.

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

الشجرة الثنائية المثالية هي واحدة من تلكالأنواع من الأشجار الثنائية حيث يجب أن يكون لكل عقدة 0 أو 2 طفل ، ويجب أن يكون مستوى كل عقدة ورقية هو نفسه.بمعنى آخر ، يتم تعريفالأشجار الثنائية المثالية في بنية البيانات على أنها تلك الأشجار التي تمتلك فيها جميع العقد الداخلية فرعين وتلك العقد التي لا تحتوي على فروع (عقد أوراق) موجودة على نفس المستوى.

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

تعلمدورات علوم البياناتعبر الإنترنت من أفضل الجامعات في العالم.اربح برامج PG التنفيذية أو برامج الشهادات المتقدمة أو برامج الماجستير لتتبع حياتك المهنية بشكل سريع.

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

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

إنها واحدة منالأنواع الأساسية للأشجار الثنائية لأنها تقدم أفضل نسبة بين عدد العقد وارتفاع الشجرة.

فيما يلي الخصائص الرئيسية لشجرة ثنائية كاملة:

• الحد الأقصى لعدد العقد هو 2 ساعة + 1 - 1.
• الحد الأدنى لعدد العقد هو ساعتان .
• الحد الأدنى للارتفاع هو log 2 (n + 1) - 1.

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

في الأشجار الثنائية المتوازنة ، يكون ارتفاع الشجرة هو 2 من إجمالي عدد العقد. افترض أن ارتفاع الشجرة هو h والعدد الإجمالي للعقد في الشجرة هو n. معادلة حساب الارتفاع h = log (n). يجب أن يكون الحد الأقصى للاختلاف في الارتفاع بين الشجرة الفرعية اليمنى والشجرة الفرعية اليسرى "1".

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

يمكنك تنفيذ التعليمات البرمجية التالية لتشغيل شجرة ثنائية متوازنة.

عقدة فئة خاصة {

قيمة int الخاصة ؛

العقدة الخاصة اليسرى ؛

حق العقدة الخاصة ؛

}

منطقية عامة متوازنة (عقدة ن) {

إذا (متوازن TreeHeight (ن)> -1)

العودة صحيح

عودة كاذبة؛

}

عمومية intancedtreeHeight (العقدة n) {

إذا (ن == خالية)

العودة 0 ؛

int h1 = BalancetreeHeight (n.right) ؛

int h2 = BalancetreeHeight (n.left) ؛

إذا (h1 == -1 || h2 == -1)

عودة -1 ؛

إذا (Math.abs (h1 - h2)> 1)

عودة -1 ؛

إذا (h1> h2)

العودة h1 + 1 ؛

إرجاع h2 + 1 ؛

}

تحقق من برامجنا في الولايات المتحدة - علوم البيانات

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

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

اقرأ مقالاتنا المشهورة حول علوم البيانات الأمريكية

خاتمة

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

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

ابدأ برحلة تعلم الآلة الخاصة بك على upGrad

إذا كنت ترغب في تعلم علوم البيانات ، يمكنك متابعة برنامج upGrad's Master of Science in Data Science . تضفي هذه الدورة التدريبية التي تبلغ مدتها 24 شهرًا مهارات مثل Python و Deploy ML Models ومعالجة BD باستخدام Spark والتحليلات التنبؤية والإحصاءات ونماذج ML الخاضعة للإشراف وغير الخاضعة للإشراف. الدورة مناسبة للمديرين الطموحين وخريجي ماجستير إدارة الأعمال والمهندسين والمهنيين في مختلف المجالات.

سيساعدك إكمال هذه الدورة التدريبية على العمل كمهندس بيانات ومحلل بيانات كبيرة ومهندس تعلم آلي وعالم بيانات.