32. أشجار البحث الثنائي (BSTs): الإدراج والبحث

شجرة البحث الثنائي (BST) هي نوع خاص من الأشجار الثنائية التي تنظم البيانات للبحث والإدراج والحذف بكفاءة.

خاصية BST

لكل عُقدة X في الشجرة:

1. يجب أن تكون قيمة جميع العُقد في شجرتها الفرعية اليسرى أقل من قيمة X.
2. يجب أن تكون قيمة جميع العُقد في شجرتها الفرعية اليمنى أكبر من قيمة X.

عملية البحث (Search Operation)

1. البدء من الجذر.
2. إذا كان الهدف مساوياً للعُقدة الحالية، فإرجاع 'صحيح' (true).
3. إذا كان الهدف أصغر، الانتقال إلى الابن الأيسر.
4. إذا كان الهدف أكبر، الانتقال إلى الابن الأيمن.

الكفاءة

• الحالة المتوسطة (شجرة متوازنة): البحث والإدراج والحذف هي O(log N). (كفاءة مماثلة للبحث الثنائي على مصفوفة).
• أسوأ حالة (شجرة منحرفة): إذا تم إدراج البيانات بترتيب مفرز، تصبح الشجرة قائمة مرتبطة، ويتدهور التعقيد إلى O(N).