Binary Search Trees (BST)
آلية العمل
هي شجرة ثنائية يتم تخزين البيانات فيها بنظام معين لتسريع البحث:
التعقيد: $O(\log n)$ في المتوسط للبحث والإضافة. (مثل Binary Search في المصفوفات ولكن مرن في الإضافة).
Decision Trees
الأشجار واتخاذ القرار
كل عقدة داخلية تمثل "سؤالاً" أو "مقارنة"، وكل ورقة (Leaf) تمثل "نتيجة" أو "قراراً".
أي خوارزمية ترتيب تعتمد على المقارنة (Comparison-based) يجب أن تقوم بـ $\lceil \log_2(n!) \rceil$ مقارنة على الأقل في أسوأ الأحوال.
$\approx O(n \log n)$.
Huffman Coding (ضغط البيانات)
Prefix Codes
لتمثيل الحروف بـ Bits متغيرة الطول (Variable Length)، يجب ألا يكون أي كود "بادئة" لكود آخر.
خطأ: a=0, b=01 (لأن 0 بداية 01).
صح: a=0, b=10, c=11.
يتم تمثيل الأكواد كأوراق في شجرة ثنائية (يسار=0، يمين=1) .
Huffman Algorithm
الهدف: الحروف الأكثر تكراراً تأخذ كوداً أقصر.
- خذ أقل حرفين تكراراً واجمعهما في شجرة صغيرة.
- مجموعهما يصبح "حرفاً جديداً".
- كرر حتى تصبح شجرة واحدة كبيرة.
Tree Traversal & Expressions
يمكن تمثيل المعادلات الرياضية كأشجار (الجذر هو العملية، والأبناء هم الأرقام).
$(+ a b)$
$(a + b)$
$(a b +)$
Is Huffman Code Unique؟
لا! شجرة هوفمان ليست وحيدة (يمكنك وضع الصفر يمين أو يسار، أو تبديل العناصر المتساوية في التكرار).
ولكن طول الكود المضغوط (عدد البتات الكلي) هو دائماً الأمثل والوحيد.
Minimax Algorithm
تستخدم أشجار القرار في الألعاب (مثل Tic-Tac-Toe).
اللاعب الأول يحاول تعظيم النتيجة (Max)، والخصم يحاول تقليلها (Min). الشجرة تمثل كل الحركات الممكنة .