شجرة ثنائية مقابل شجرة البحث الثنائية: الفرق بين شجرة ثنائية وشجرة بحث ثنائية

مقدمة

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

تُستخدم الأشجار بشكل أساسي لتمثيل البيانات من خلال إظهار علاقة هرمية بين العناصر. على سبيل المثال ، جدول المحتويات ، شجرة العائلة. من الناحية الفنية ، يمكن تعريف الشجرة على أنها مجموعة محدودة "T" لعقد واحد أو أكثر بحيث يتم تعيين عقدة كجذر للشجرة وتنقسم العقد الأخرى إلى n> = 0 مجموعات منفصلة T1 ، T2 ، T3 ، T4 .... Tn وتسمى بالأشجار الفرعية أو الأبناء لتلك العقدة الجذرية.

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

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

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

1. عنصر البيانات - يخزن قيمة البيانات التي سيتم تخزينها بواسطة العقدة.
2. المؤشر إلى الطفل الأيسر - يخزن المرجع (أو العنوان) إلى عقدة الطفل الأيسر.
3. المؤشر إلى الطفل الأيمن - يخزن المرجع إلى العقدة اليمنى التابعة.

بهذه الطريقة ، يتم دمج عدة عقد معًا لبناء شجرة ثنائية.

يمكن تمثيل الشجرة الثنائية على النحو التالي:

مصدر

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

تحقق من: أنواع الشجرة الثنائية

المصطلحات المستخدمة في Binary Tree

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

عقدة الجذر : العقدة العلوية للشجرة الثنائية.

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

العقدة الفرعية: إذا كان للعقدة سلف ، فإنها تُعرف باسم العقدة الفرعية.

العقدة الورقية : تسمى العقدة التي لا تحتوي على أي عقدة فرعية كعقدة طرفية.

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

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

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

اقرأ أيضًا: خوارزمية البحث الثنائي: الوظيفة ، الفوائد ، تعقيد الوقت والمكان

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

كما يوحي الاسم ، فإن Binary Search Tree أو BST عبارة عن شجرة تُستخدم في فرز البيانات واسترجاعها والبحث عنها. وهو أيضًا نوع من بنية البيانات غير الخطية حيث يتم ترتيب العقد بترتيب معين. ومن ثم ، يطلق عليها أيضًا اسم " الشجرة الثنائية المرتبة ". لها الخصائص التالية:

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

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

مصدر

في الشكل أعلاه ، نرى أن قيمة عقدة الجذر هي 8. مع مزيد من التدقيق ، لوحظ أن جميع القيم الموجودة في الشجرة الفرعية اليسرى أقل من قيمة عقدة الجذر وأن جميع القيم الموجودة في الشجرة الفرعية اليمنى لها القيم الأكبر من عقدة الجذر. علاوة على ذلك ، من الملاحظ أن كل قيمة في شجرة البحث الثنائية فريدة ولا توجد تكرارات. وبالتالي ، يتم التحقق من خصائص Binary Search Tree المذكورة أعلاه.

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

عملية البحث في BST -

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

مصدر

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

الخطوة الأولى هي حساب القيمة الوسطى للمصفوفة ومقارنتها بالقيمة التي سيتم البحث عنها ، 9 في حالتنا. يتم ذلك عن طريق حساب n / 2 ، حيث n هو العدد الإجمالي للعناصر في المصفوفة (BST) وهو 6. وبالتالي ، فإن العنصر الثالث هو العنصر الأوسط وهو 5.

الآن بعد أن تمت مقارنة العنصر الأوسط بـ 9 وبما أنه لا يساوي (أكبر) ، سيتم تنفيذ عملية البحث على المصفوفة الصحيحة. وبهذه الطريقة يتم تقليل عملية البحث إلى النصف كما هو موضح أدناه:

في الخطوة التالية ، تم حساب العنصر الأوسط ووجد أنه 9 ، وهو ما يطابق العنصر المراد البحث عنه.

شجرة ثنائية مقابل شجرة بحث ثنائية -

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

خاتمة

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

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

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