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

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

ما هي الأشجار الثنائية؟

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

تحتوي جميع العقد في الشجرة الثنائية على ثلاثة مكونات أساسية -

• عنصر بيانات
• مرجع صحيح
• مرجع يسار

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

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

تحقق من: أفكار مشروع علوم البيانات للمبتدئين

خصائص مهمة للعقد في الأشجار الثنائية

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

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

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

تعرف على المزيد: هياكل البيانات والخوارزمية في بايثون

ما هي شجرة البحث الثنائية؟

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

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

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

1. التمثيل المرتبط

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

في هذا التمثيل ، تتكون كل عقدة من ثلاثة أجزاء مختلفة -

• المؤشر الذي يشير إلى العقدة اليمنى ،
• المؤشر الذي يشير إلى العقدة اليسرى ،
• عنصر البيانات.

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

2. التمثيل المتسلسل

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

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

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

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

قراءة: هياكل البيانات الستة الأكثر استخدامًا في R

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

1. طريقة مثالية للتعامل مع الطريقة الهرمية لتخزين البيانات
2. تعكس العلاقات الهيكلية الموجودة في مجموعة البيانات المحددة
3. جعل الإدراج والحذف أسرع من القوائم والمصفوفات المرتبطة
4. طريقة مرنة للاحتفاظ بالبيانات ونقلها
5. تُستخدم لتخزين أكبر عدد ممكن من العقد
6. تكون أسرع من القوائم المرتبطة وأبطأ من المصفوفات عندما يتعلق الأمر بالوصول إلى العناصر

خاتمة

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

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