الدرس 12: الأشجار وأشجار البحث الثنائية
تخيّل شجرة العائلة، أو مجلدات داخل مجلدات: هناك شيء 'في الأعلى' يتفرّع إلى عناصر 'في الأسفل'. هذه 'شجرة' — كل نقطة فيها هي 'عقدة' (node). في 'شجرة البحث الثنائية' (BST) تكون لكل عقدة قيم أصغر على يسارها وقيم أكبر على يمينها — تمامًا مثل البحث عن كلمة في القاموس: افتح في المنتصف، وتجاوز النصف. عندما
الـ BST مثل البحث عن كلمة في القاموس: افتح في المنتصف، وإذا كانت الكلمة تأتي 'قبل ذلك' فإنك تتجاوز النصف الأيمن بأكمله دفعةً واحدة. كل مقارنة توفّر نصف العمل — لكن فقط إذا كانت الصفحات مقسومة بالتساوي.
- صنف (class)
- قالب لصندوق صغير بحقول. class TreeNode تعرّف صندوقًا بثلاثة حقول: val (القيمة) و left/right (الأطفال). TreeNode(5) تنشئ صندوقًا كهذا، و self تعني ببساطة "هذا الصندوق" (نفس فكرة درس القوائم المترابطة).
- شجرة البحث الثنائية
- شجرة ثنائية حيث تكون، لكل عقدة، جميع القيم في الشجرة الفرعية اليسرى أصغر وجميع القيم في الشجرة الفرعية اليمنى أكبر.
- مرور الشجرة
- زيارة كل عقدة في الشجرة بترتيب محدّد. inorder (يسار، عقدة، يمين) على BST يُنتج القيم مرتّبة.
- شجرة متوازنة
- شجرة يقارب ارتفاعها log n، لذا يستغرق البحث O(log n). الشجرة المنحرفة تفقد تلك الميزة وتصل إلى O(n).
