البحث الذكي: Linked List ضد BST
تقارن بين البحث الخطي والبحث داخل BST.
أهداف الدرس
- تفهم لماذا BST قد تكون أسرع.
- تميّز O(n) عن O(log n) بشكل بصري.
- تتعلم أن السرعة تعتمد على شكل البيانات.
القصة
عندك قائمة أرقام طويلة. في Linked List يجب أن تمر غالبًا عنصرًا عنصرًا. في BST تسأل سؤالًا ذكيًا كل مرة: هل الرقم أصغر أم أكبر؟ فتتخلص من نصف الطريق تقريبًا.
الفكرة البرمجية
البحث في Linked List خطي O(n) لأنه لا توجد طريقة للقفز للعنصر المطلوب. في BST المتوازنة، كل خطوة تختار فرعًا واحدًا وتترك الفرع الآخر.
تخيلها بصريًا
في BST: تبحث عن 60. تبدأ 50: 60 أكبر، اذهب يمينًا. تصل 70: 60 أصغر، اذهب يسارًا. تصل 60.
قارن عمليًا
- في Linked List أضف 20,30,40,50,60 ثم Search(60).
- لاحظ أنه يمر على عدة عقد.
- في BST أدخل 50,30,70,60 ثم Search(60).
- لاحظ أن الطريق أقصر.
تحدي الدرس
متى قد تصبح BST سيئة مثل Linked List؟ فكر قبل الدرس التالي.
تحقق سريع
- لماذا Linked List بحثها O(n)؟
الإجابة: لأنها تمر من عقدة إلى التالية - ما ميزة BST المتوازنة؟
الإجابة: تقلل عدد الخطوات أثناء البحث