الشجرة اللاحقة (Trie)

المشكلة: بحث سريع بين آلاف الكلمات ذات بادئات مشتركة

فكّر بخاصية الإكمال التلقائي بمحرّك بحث: تكتب "برم" فيقترح فورًا "برمجة"، "برمج"، "برمجيات". جدول التجزئة (hash table) يجيب بسرعة O(1) عن "هل هذه الكلمة موجودة بالضبط؟"، لكنه لا يساعد بسؤال "ما كل الكلمات التي تبدأ بـ...؟" بدون فحص كل كلمة. هنا يأتي Trie (يُلفَظ "تراي"، ويُعرف أيضًا بالشجرة اللاحقة أو Prefix Tree): هيكل بيانات مصمّم خصيصًا للبحث بالبادئة.

الفكرة: كل حرف مسار، والكلمات المشتركة تتشارك فروعًا

كل عقدة تمثّل حرفًا واحدًا، والمسار من الجذر لأي عقدة يمثّل بادئة. الكلمات التي تشترك ببادئة (مثل "بر" في "برمجة" و"برق") تتشارك نفس الفرع حتى نقطة الاختلاف — توفير كبير بالذاكرة مقارنة بتخزين كل كلمة منفصلة.

إدراج: "بر"، "برمجة"، "برق"

        (جذر)
          |
          ب
          |
          ر  ← نهاية كلمة "بر"
         / \
        م   ق  ← نهاية كلمة "برق"
        |
        ج
        |
        ة  ← نهاية كلمة "برمجة"

التنفيذ

كل عقدة تحتاج: خريطة من حرف لعقدة الابن التالية، وعلامة "نهاية كلمة" (لأن "بر" نفسها كلمة صالحة، رغم أنها بادئة لكلمة أطول "برمجة").

class TrieNode:
    def __init__(self):
        self.children = {}   # حرف -> TrieNode
        self.is_end_of_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end_of_word

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, text):
        node = self.root
        for char in text:
            if char not in node.children:
                return None
            node = node.children[char]
        return node


trie = Trie()
for word in ["بر", "برمجة", "برق"]:
    trie.insert(word)

print(trie.search("برمجة"))     # True
print(trie.search("برم"))       # False — "برم" لم تُدرَج ككلمة كاملة
print(trie.starts_with("برم"))  # True — بادئة موجودة (تقود لـ "برمجة")

التعقيد

كل من insert وsearch وstarts_with يعمل بتعقيد O(L) حيث L طول الكلمة/البادئة المدخَلة — مستقلّ تمامًا عن عدد الكلمات المخزَّنة بالكامل. هذا أسرع من شجرة بحث ثنائية متوازنة (التي تحتاج مقارنات كاملة للكلمة بتعقيد O(L × log n))، ولا يحتاج دالة تجزئة أو معالجة تصادمات كما جداول التجزئة.

الثمن: الذاكرة

عيب Trie الرئيسي: استهلاك ذاكرة أكبر من جدول التجزئة، لأن كل عقدة قد تحتفظ بعدة مؤشرات لأبناء محتملين حتى لو استُخدم القليل منها فعليًا. تحسينات مثل Compressed Trie (دمج السلاسل الأحادية الفرع بعقدة واحدة) تخفّف هذا لكنها تتجاوز نطاق هذا الدرس التمهيدي.

التطبيقات الحقيقية

• الإكمال التلقائي بمحركات البحث وحقول النصوص.
• التدقيق الإملائي وقواميس الكلمات.
• جداول توجيه الشبكات (IP Routing): مطابقة أطول بادئة لعنوان IP.
• محركات البحث النصي وفهرسة الكلمات المفتاحية.

أخطاء شائعة

• الخلط بين search (هل هذه كلمة كاملة مُدرَجة؟) وstarts_with (هل هذه بادئة صالحة لأي كلمة؟) — نسيان فحص is_end_of_word بـ search يُعيد نتائج خاطئة (يعتبر أي بادئة كلمة صالحة).
• استخدام Trie لمسائل لا تحتاج بحث بادئة أصلًا (مثل "هل هذه الكلمة موجودة بالضبط؟" فقط) — جدول التجزئة أبسط وأقل استهلاكًا للذاكرة بهذه الحالة.
• تجاهل حجم الذاكرة مع أبجديات كبيرة (كل حروف Unicode مثلًا) — استخدام خريطة ديناميكية (dict) للأبناء بدل مصفوفة ثابتة الحجم يوفّر ذاكرة كثيرة هنا.

🎯 التالي: الخلاصة الشاملة لمسار هياكل البيانات والخوارزميات.