كارثة الشجرة المائلة
تعرف أن BST ليست سريعة دائمًا إذا أصبحت غير متوازنة.
أهداف الدرس
- تفهم معنى Unbalanced Tree.
- تعرف لماذا Worst Case في BST هو O(n).
- تستخدم تنبيه المحاكي لفهم المشكلة.
القصة
أدخل مهندس الأرقام بالترتيب: 10 ثم 20 ثم 30 ثم 40 ثم 50. بدل أن تصبح شجرة جميلة، تحولت إلى سلسلة مائلة مثل Linked List. هنا انهار الوعد الجميل: O(log n).
الفكرة البرمجية
BST تكون ممتازة عندما تكون متوازنة تقريبًا. إذا أدخلت القيم بترتيب تصاعدي أو تنازلي، قد تصبح الشجرة طويلة جدًا، ويصبح البحث مثل المرور على قائمة.
تخيلها بصريًا
10 → 20 → 30 → 40 → 50 كلها جهة اليمين. لا يوجد تفرع حقيقي.
اصنع المشكلة
- اختر BST.
- Insert: 10, 20, 30, 40, 50, 60.
- راقب التنبيه الأصفر في المحاكي.
- ابحث عن 60 ولاحظ عدد الخطوات.
تحدي الدرس
كيف يمكن أن تتجنب بناء شجرة مائلة؟ اكتب فكرة قبل البحث عن AVL أو Red-Black Tree.
تحقق سريع
- متى يصبح Worst Case في BST هو O(n)؟
الإجابة: عندما تصبح الشجرة غير متوازنة - هل BST أسرع دائمًا من Linked List؟
الإجابة: لا