المستوى المطلوب: متوسط — هذا المقال موجّه لمن يعرف أساسيات البرمجة (functions, dictionaries, recursion) ويرغب في فهم بنية بيانات Trie وإزاي تستخدمها في مشكلة حقيقية زي autocomplete أو البحث بالبادئات.
لو تطبيقك بيعمل autocomplete بـ SELECT * FROM products WHERE name LIKE 'iph%' على جدول مليون صف، الاستعلام بياخد متوسط 380ms في PostgreSQL مع index. Trie بترد نفس النتائج في أقل من 4ms من الذاكرة بدون لمس قاعدة البيانات. هنا الفرق وإزاي تبني واحدة بنفسك.
Trie: بنية البيانات اللي بتخلي البحث بالبادئة شبه فوري
المشكلة باختصار
تطبيقك فيه search bar بيعمل suggest كل ما المستخدم يكتب حرف. كل keystroke بيضرب قاعدة البيانات. لو الجدول كبير، السيرفر بيختنق والمستخدم بيشوف lag واضح. الحل التقليدي بـ LIKE 'prefix%' ممكن يستفيد من B-tree index، لكن كل query لسه بيمر عبر شبكة + parser + planner. Trie بيخلي العملية كلها in-memory في O(L) حيث L هو طول البادئة، مش حجم الـ dataset كله.
تمثيل تقريبي قبل التعريف العلمي
تخيّل قاموس ورقي ضخم. لو سألتك عن كلمة بتبدأ بـ "kit"، أنت ما هتقرأش كل صفحة. هتفتح حرف K، بعدين I، بعدين T، وهتلاقي كل الكلمات اللي بتبدأ بكده في صفحة محدودة. ده بالظبط اللي Trie بيعمله: شجرة حروف، كل عقدة بتمثل حرف، والمسار من الجذر لأي عقدة بيبني كلمة. مفيش كلمة بتتقارن بالكلمات التانية، أنت بس بتمشي على الحروف.
التعريف العلمي الدقيق
Trie (تنطق "tray"، اختصار لكلمة Retrieval) هي شجرة prefix tree حيث كل عقدة تمثل حرف واحد. كل مسار من الجذر إلى عقدة معلَّمة كنهاية كلمة يمثل كلمة كاملة. تعقيد البحث عن كلمة طولها L هو O(L) بغض النظر عن عدد الكلمات الكلي N في البنية. تعقيد الإدراج كذلك O(L). تعقيد البحث بالـ prefix لإرجاع كل الكلمات اللي تبدأ ببادئة معينة هو O(L + K) حيث K عدد النتائج المطابقة. بالمقارنة، البحث الخطي في array هو O(N × L)، والبحث في B-tree هو O(L × log N).
كود Python شغّال — انسخه واشتغل
class TrieNode:
__slots__ = ("children", "is_end")
def __init__(self):
self.children = {}
self.is_end = 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, limit: int = 10) -> list[str]:
node = self.root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
results = []
self._collect(node, prefix, results, limit)
return results
def _collect(self, node, current, results, limit):
if len(results) >= limit:
return
if node.is_end:
results.append(current)
for ch, child in node.children.items():
self._collect(child, current + ch, results, limit)
trie = Trie()
products = ["iphone", "ipad", "imac", "macbook", "airpods", "ipod"]
for p in products:
trie.insert(p)
print(trie.starts_with("ip"))
# ['iphone', 'ipad', 'ipod']
