ما هي تجربة البادئة (Trie/Prefix Tree) ومتى تكون مفيدة؟

Question

Accepted Answer

**Trie** (تجربة البادئة) هي شجرة حيث يمثل كل **edge** حرفاً وكل **مسار من الجذر** يتكون من بادئة. الكلمات التي تشارك بادئة مشتركة تشارك نفس المسار، مما يجعل بحث البادئة سريعاً جداً.

## الهيكل

```text
Insert "cat", "car", "dog":
        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*       (* marks end-of-word)
```

## الكود

```python
class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):           # O(L), L = word length
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
    def starts_with(self, prefix):    # O(L)
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True
```

## التعقيد الزمني

| العملية | الوقت |
|---|---|
| insert | O(L) |
| search | O(L) |
| prefix query | O(L) |

حاسماً، التكلفة تعتمد على **طول الكلمة L**، وليس على عدد الكلمات المحفوظة.

## المقارنات

- **المزايا:** بحث سريع عن البادئات؛ إكمال تلقائي؛ البادئات المشتركة توفر مساحة للكلمات المشابهة.
- **العيوب:** احتمالية عالية للذاكرة لكل عقدة (خريطة أطفال لكل عقدة)؛ قد تستخدم مساحة أكثر من hash set للمفاتيح غير المرتبطة.

## لماذا يهمك

تقوم Tries بتشغيل الإكمال التلقائي والتدقيق الإملائي وجداول توجيه IP والبحث القائم على القاموس حيث يكون مطابقة **البادئة** مهمة.

عندما تجيب مجموعة hash فقط على "هل هناك تطابق دقيق؟"، فإن Trie يجيب بكفاءة على "ما الكلمات التي تبدأ بـ X؟".