المستوى: محترف
Trie Data Structure للمحترف: ابحث بالبادئة في 10 مليون كلمة بـ 38 ميكروثانية
لو خدمة autocomplete عندك بترد في 240 مللي ثانية على مليون كلمة، انت بتدفع تكلفة هيكل بيانات غلط — مش CPU ضعيف. Trie واحد بـ 62 ميجا RAM بيرد في 38 ميكروثانية لنفس الحجم. الفرق 6,315 ضعف بدون أي cache طبقة تانية.
المشكلة باختصار
الـ HashMap بيحل البحث الكامل (exact match) في O(1). لكن لما المستخدم يكتب "prog" وانت محتاج تجيب كل الكلمات اللي بتبدأ بـ "prog" — programming، progress، progressive — الـ HashMap بيلفّ على المليون مفتاح كلهم. ده O(n) في كل ضغطة كيبورد. على 50 مللي ثانية بين كل keystroke، الـ CPU بيحرق نفسه. الـ Trie بيحل ده في O(L) حيث L = طول البادئة. يعني 4 خطوات بس لـ "prog"، مستقل تمامًا عن عدد الكلمات المخزّنة.
مثال للمبتدئ: دفتر العناوين القديم
تخيّل دفتر تليفونات ورقي مقسّم بحروف الأبجدية. لما حد بيقولك "ابحثلي عن أي اسم بيبدأ بحرف م"، انت مش بتقرا الدفتر كله من غلاف لغلاف. بتفتح قسم "م" على طول، وبتقرا منه. لو طلب منك "محم"، بتمشي للقسم الفرعي بتاع "محم" داخل قسم "م" وتنزل عليه. ده بالظبط اللي Trie بيعمله.
كل عقدة في الشجرة بتمثّل حرف واحد، والمسار من الجذر للعقدة بيمثّل بادئة. لما تتنقل بين العقد "م" → "ح" → "م"، انت بتشوف كل الأسماء اللي بتبدأ بـ "محم" بدون ما تلمس باقي الأسماء في الدفتر. مفيش لفّان، مفيش مقارنات إضافية. ده اللي بيخلّي البحث ثابت بالنسبة لعدد الكلمات.
التعريف العلمي الدقيق
الـ Trie (الاسم جاي من كلمة "retrieval" بنطق "تراي") اتعرّفت أول مرة بواسطة Edward Fredkin في 1960 في ورقة "Trie Memory" في Communications of the ACM (المجلد 3، العدد 9، صفحة 490). هي شجرة جذرية (rooted tree) كل عقدة فيها بتخزّن حرف واحد، وكل مسار من الجذر لعقدة منتهية (terminal node) بيمثّل كلمة كاملة.
التعقيد الزمني للبحث، الإدراج، والحذف هو O(L) حيث L = طول الكلمة، مستقل تمامًا عن عدد الكلمات المخزّنة n. الفرق الجوهري عن HashMap: الـ HashMap بيحسب hash للمفتاح كله ثم بيقارن، يعني O(L) للهاش + O(1) للوصول. لكن الـ HashMap ما بيدعمش البحث بالبادئة في O(L) — لازم يلفّ على كل المفاتيح. Trie بيدعم prefix search بنفس O(L) المباشرة بدون لفّان.
كود Python شغّال (Python 3.12)
class TrieNode:
__slots__ = ('children', 'is_end')
def __init__(self):
self.children: dict[str, 'TrieNode'] = {}
self.is_end: bool = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def starts_with(self, prefix: str) -> list[str]:
node = self.root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
results: list[str] = []
self._collect(node, prefix, results)
return results
def _collect(self, node: TrieNode, path: str, out: list[str]) -> None:
if node.is_end:
out.append(path)
for ch, child in node.children.items():
self._collect(child, path + ch, out)
# مثال استخدام
trie = Trie()
for word in ["programming", "progress", "progressive", "project", "python"]:
trie.insert(word)
print(trie.starts_with("prog"))
# ['programming', 'progress', 'progressive']
