أشجار Trie للبحث عن البادئات
تخزين بادئات الكلمات والاستعلام عنها بسرعة
أشجار Trie للبحث عن البادئات درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
تخزين الكلمات بذكاء
إن شجرة البادئات هي شجرة تخزن الكلمات من خلال مشاركة البادئات المشتركة. وتتيح الإجابة عن استعلامات البادئات بسرعة هائلة. 🌳
لماذا لا نستخدم مجموعة فحسب
تجيب المجموعة عن عمليات البحث عن الكلمات الكاملة، لكن أشجار البادئات تجيب أيضًا عن استعلامات البادئات، مثل: هل تبدأ أي كلمة بـ pre؟
العُقد والحواف
تمثل كل عقدة موضعًا في كلمة ما، وتحمل كل حافة تسمية مكوّنة من محرف على المسار من الجذر.
الأبناء في قاموس
في Python، أسهل تمثيل لـالعقدة هو قاموس يربط محرفًا بعقدته الابنة. وهو تمثيل واضح ومرن.
root = {}إدراج كلمة
من أجل الإدراج، مرّوا على المحارف واحدًا تلو الآخر وأنشئوا ابنًا كلما كان مفقودًا.
node = root
for c in word:
node = node.setdefault(c, {})تحديد نهايات الكلمات
بعد الإدراج، عيّنوا علامة end حتى تتمكنوا من التمييز بين كلمة كاملة وبادئة فقط.
node['#'] = Trueالبحث عن كلمة كاملة
من أجل البحث، اتبعوا المحارف؛ فإذا كانت أي خطوة مفقودة، فالكلمة غير موجودة. ثم افحصوا علامة النهاية.
for c in word:
if c not in node:
return False
node = node[c]التحقق من بادئة
استعلام البادئة هو المسار نفسه، لكنكم تتجاوزون فحص علامة النهاية. والوصول إلى العقدة الأخيرة يعني أن الإجابة نعم.
التعقيد الزمني
تستغرق عمليتا الإدراج والبحث O(L)، حيث L طول الكلمة، بغض النظر عن عدد الكلمات المخزنة. فالطول هو العامل المهم.
عدّ الكلمات حسب البادئة
خزّنوا عددًا عند كل عقدة للإجابة فورًا عن عدد الكلمات المخزنة التي تشترك في بادئة معينة.
متى تفيد أشجار البادئات
تُستخدم أشجار البادئات في الإكمال التلقائي، والتحقق من القواميس، ومسائل تعظيم XOR على البتات. وهي أداة أساسية في مسائل السلاسل بالمسابقات.
تحقق سريع
تأكدوا من التكلفة الفعلية للبحث في شجرة البادئات.
مراجعة: إتمام أشجار البادئات
يمكنكم الآن بناء شجرة بادئات، وإجراء الإدراج والبحث في O(L)، والإجابة بسرعة عن استعلامات البادئات والعدّ. 🌟
الأسئلة الشائعة
هل درس «أشجار Trie للبحث عن البادئات» مجاني؟
نعم — نص درس «أشجار Trie للبحث عن البادئات» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «أشجار Trie للبحث عن البادئات»؟
تخزين بادئات الكلمات والاستعلام عنها بسرعة تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «أشجار Trie للبحث عن البادئات»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- دالة بادئة KMP
- تجزئة السلاسل متعددة الحدود
- دالة Z للبحث عن الأنماط
- أشجار Trie للبحث عن البادئات