تعد شجرة البحث الثنائية إحدى هياكل البيانات المختلفة التي تساعدنا في تنظيم البيانات وفرزها. إنها طريقة فعالة لتخزين البيانات في تسلسل هرمي ومرنة للغاية.
في هذه المقالة ، سنلقي نظرة فاحصة على كيفية عملها - جنبًا إلى جنب مع خصائصها وتطبيقاتها.
ما هي شجرة البحث الثنائية؟
شجرة البحث الثنائية هي بنية بيانات مكونة من عقد - تشبه القوائم المرتبطة. يمكن أن يكون هناك نوعان من العقد: أحد الوالدين والطفل. العقدة الجذرية هي نقطة البداية للبنية المتفرعة إلى عقدتين فرعيتين ، تسمى العقدة اليسرى والعقدة اليمنى.
لا يمكن الإشارة إلى كل عقدة إلا من خلال والدتها ، ويمكننا اجتياز عقد الشجرة اعتمادًا على الاتجاه. شجرة البحث الثنائية لها ثلاث خصائص رئيسية:
- العقدة اليسرى أصغر من العقدة الأم.
- العقدة اليمنى أكبر من أصلها.
- يجب أن تكون الأشجار الفرعية اليمنى واليسرى عبارة عن أشجار بحث ثنائية.
يتم تحقيق شجرة بحث ثنائية مثالية عندما يتم ملء جميع المستويات ، ولكل عقدة عقدة فرعية يمنى ويسرى.
متعلق ب: مكتبات علوم البيانات لبايثون يجب على كل عالم بيانات استخدامها
العمليات الأساسية لشجرة البحث الثنائي
الآن لديك فكرة أفضل عن ماهية شجرة البحث الثنائية ، يمكننا إلقاء نظرة على عملياتها الأساسية أدناه.
1. عملية البحث
يتيح لنا البحث تحديد قيمة معينة موجودة في الشجرة. يمكننا استخدام نوعين من عمليات البحث: البحث الأول (BFS) والبحث المتعمق الأول (DFS). البحث ذو النطاق الأول عبارة عن خوارزمية بحث تبدأ في العقدة الجذرية وتنتقل أفقيًا ، جنبًا إلى جنب ، حتى يتم العثور على الهدف. تتم زيارة كل عقدة مرة واحدة خلال هذا البحث.
من ناحية أخرى ، يجتاز بحث العمق أولاً الشجرة عموديًا - بدءًا من عقدة الجذر والعمل أسفل فرع واحد. إذا تم العثور على الهدف ، تنتهي العملية. ولكن إذا لم يكن كذلك ، فإنه يبحث في العقد الأخرى.
2. أدخل العملية
تستخدم عملية الإدراج عملية البحث لتحديد الموقع الذي يجب إدخال العقدة الجديدة فيه. تبدأ العملية من العقدة الجذرية ، ويبدأ البحث حتى يتم الوصول إلى الوجهة. هناك ثلاث حالات يجب مراعاتها مع الإدراج.
- الحالة 1: في حالة عدم وجود عقدة. العقدة التي سيتم إدراجها ستصبح العقدة الجذرية.
- الحالة 2: لا يوجد أطفال. في هذه الحالة ، ستتم مقارنة العقدة بعقدة الجذر. إذا كان أكبر ، فسيصبح الطفل المناسب ؛ وإلا سيصبح الطفل الأيسر.
- الحالة الثالثة: وجود الجذر وأبنائه. ستتم مقارنة العقدة الجديدة بكل عقدة في مسارها لتحديد العقدة التي ستزورها بعد ذلك. إذا كانت العقدة أكبر من عقدة الجذر ، فسوف تنتقل إلى أسفل الشجرة الفرعية اليمنى أو إلى اليسار. وبالمثل ، يتم إجراء مقارنات على كل مستوى لتحديد ما إذا كان سيتجه يمينًا أم يسارًا حتى يصل إلى وجهته.
3. حذف العملية
تُستخدم عملية الحذف لإزالة عقدة معينة داخل الشجرة. يعتبر الحذف أمرًا صعبًا لأنه بعد إزالة العقدة ، يجب إعادة تنظيم الشجرة وفقًا لذلك. هناك ثلاث حالات رئيسية يجب مراعاتها:
- الحالة 1: حذف عقدة طرفية. العقدة الطرفية هي عقدة بدون أي توابع. هذا هو أسهل إزالته لأنه لا يؤثر على أي عقدة أخرى ؛ نحن ببساطة نقطع الشجرة حتى نصل إليها ونحذفها.
- الحالة 2: حذف عقدة مع طفل واحد. سيؤدي حذف أحد الوالدين مع عقدة واحدة إلى اتخاذ الطفل موقعه ، وسترتفع جميع العقد اللاحقة إلى مستوى أعلى. لن يكون هناك أي تغيير في هيكل الأشجار الفرعية.
- الحالة 3: حذف عقدة مع طفلين. عندما يتعين علينا إزالة عقدة مع طفلين ، يجب علينا أولاً إيجاد عقدة لاحقة يمكنها أن تأخذ موقعها. يمكن أن تحل عقدتان محل العقدة التي تمت إزالتها ، والعقدة اللاحقة أو السابقة. والشجرة اللاحقة للداخل هي الفرع الأيمن الموجود في أقصى اليسار ، والسلف الوارد في الترتيب هو الطفل الموجود في أقصى اليسار للشجرة الفرعية. نقوم بنسخ محتويات الوريث / السلف إلى العقدة وحذف الوريث / السلف الوارد.
متعلق ب: كيفية بناء هياكل البيانات باستخدام فئات JavaScript ES6
كيفية اجتياز شجرة بحث ثنائية
الاجتياز هو العملية التي نتنقل من خلالها في شجرة بحث ثنائية. يتم ذلك لتحديد موقع عنصر معين أو طباعة مخطط تفصيلي للشجرة. نبدأ دائمًا من عقدة الجذر وعلينا اتباع الحواف للوصول إلى العقد الأخرى. يجب اعتبار كل عقدة شجرة فرعية ، وتتكرر العملية حتى تتم زيارة جميع العقد.
- الاجتياز بالترتيب: سيؤدي العبور بالترتيب إلى إنتاج الخريطة بترتيب تصاعدي. بهذه الطريقة ، نبدأ من الشجرة الفرعية اليسرى وننتقل إلى الجذر والشجرة الفرعية اليمنى.
- اجتياز الطلب المسبق: في هذه الطريقة ، تتم زيارة عقدة الجذر أولاً ، متبوعة بالشجرة الفرعية اليسرى والشجرة الفرعية اليمنى.
- الاجتياز بعد الطلب: يتضمن هذا الاجتياز زيارة عقدة الجذر أخيرًا. نبدأ من الشجرة الفرعية اليسرى ، ثم الشجرة اليمنى ، ثم عقدة الجذر.
تطبيقات العالم الحقيقي
لذا ، كيف نستخدم خوارزميات شجرة البحث الثنائية؟ كما يمكن تخيلها ، فهي فعالة للغاية في البحث والفرز. أعظم قوة للأشجار الثنائية هي هيكلها المنظم. إنه يسمح بإجراء البحث بسرعات ملحوظة عن طريق تقليل كمية البيانات التي نحتاج إلى تحليلها بمقدار النصف لكل تمريرة.
تسمح لنا أشجار البحث الثنائية بالحفاظ بكفاءة على مجموعة بيانات متغيرة ديناميكيًا في شكل منظم. بالنسبة للتطبيقات التي تحتوي على بيانات يتم إدراجها وإزالتها بشكل متكرر ، فهي مفيدة جدًا. تستخدم محركات ألعاب الفيديو خوارزمية تستند إلى الأشجار المعروفة باسم قسم الفضاء الثنائي للمساعدة في عرض الكائنات بشكل منظم. يستخدم Microsoft Excel ومعظم برامج جداول البيانات الأشجار الثنائية كهيكل بيانات أساسي.
قد تفاجأ بمعرفة أن شفرة مورس تستخدم شجرة بحث ثنائية لتشفير البيانات. سبب بارز آخر لأشجار البحث الثنائية مفيدة جدًا هو تبايناتها المتعددة. أدت مرونتهم إلى إنشاء العديد من المتغيرات لحل جميع أنواع المشاكل. عند استخدامها بشكل صحيح ، تعد أشجار البحث الثنائية رصيدًا رائعًا.
أشجار البحث الثنائية: نقطة البداية المثالية
تتمثل إحدى الطرق الرئيسية لقياس خبرة المهندس في معرفتهم وتطبيق هياكل البيانات. هياكل البيانات مفيدة ويمكن أن تساعد في إنشاء نظام أكثر كفاءة. Binary Search Trees عبارة عن مقدمة رائعة لهياكل البيانات لأي مطور يبدأ.
هل تريد فهم مصفوفات JavaScript ولكن لا يمكنك التعامل معها؟ تحقق من أمثلة مصفوفة JavaScript الخاصة بنا للحصول على إرشادات.
اقرأ التالي
- برمجة
- برمجة
- أدوات البرمجة
ماكسويل هو مطور برمجيات يعمل ككاتب في أوقات فراغه. متحمس للتكنولوجيا يحب الانغماس في عالم الذكاء الاصطناعي. عندما لا يكون مشغولاً بعمله ، فإنه يتوقف عن القراءة أو ممارسة ألعاب الفيديو.
اشترك في نشرتنا الإخبارية
انضم إلى النشرة الإخبارية لدينا للحصول على نصائح تقنية ومراجعات وكتب إلكترونية مجانية وصفقات حصرية!
انقر هنا للاشتراك
