الفئة TrieNode: الإدراج والبحث
أنشئ TrieNode مع قاموس children وعلامة is_end، ونفّذ insert وexact-search، وحلّل الزمن O(m) لكل عملية، حيث m هو طول الكلمة.
الفئة TrieNode: الإدراج والبحث درس مجاني في DSA Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في DSA Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
ما هي Trie؟
إن Trie، أو شجرة البادئات، بنية بيانات على شكل شجرة، تمثل فيها كل عقدة حرفًا. تُخزَّن الكلمات بربط حروفها من الجذر إلى الورقة. ويمثل الجذر سلسلة فارغة. يمثّل كل مسار من الجذر إلى عقدة is_end = True كلمةً مخزّنة. وتُعد Tries مثالية لـالاستعلامات المعتمدة على البادئات، مثل الإكمال التلقائي والتدقيق الإملائي وتوجيه IP، إذ تتفوق على جداول التجزئة في حالات الاستخدام هذه.
تصميم الفئة TrieNode
تحتوي TrieNode على حقلين: children — قاموس يربط الحروف بعقد TrieNode الابنة — وis_end — قيمة منطقية تحدد ما إذا كانت هذه العقدة نهاية كلمة مخزّنة. ويؤدي استخدام قاموس بدلًا من مصفوفة ثابتة من 26 خانة إلى تعميم البنية لتدعم أي مجموعة محارف، كما يوفر الذاكرة في Tries قليلة الكثافة. تمثل كل عقدة في Trie موضع حرف واحد بالضبط في الكلمات المتفرعة منها.
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # True if a word ends here
class Trie:
def __init__(self):
self.root = TrieNode()
def __repr__(self):
return f'Trie(root with {len(self.root.children)} children)'
t = Trie()
print(t) # Trie(root with 0 children)عملية الإدراج
لإدراج كلمة، ابدأ من الجذر وتتبّع المسار، وأنشئ TrieNode جديدة لكل حرف غير موجود مسبقًا في children الخاصة بالعقدة الحالية. بعد معالجة جميع الحروف، اضبط is_end = True في العقدة النهائية. يؤدي إدراج 'apple' و'app' إلى إنشاء السلسلة a→p→p→l→e (مع is_end=True للكلمة 'apple')، مع وضع is_end=True أيضًا على الحرف p في الموضع 3 للكلمة 'app'.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = 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 = True
t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)عملية البحث
للبحث عن كلمة مطابقة تمامًا، تتبّع Trie باتباع كل حرف. إذا كان أي حرف مفقودًا من children الخاصة بالعقدة الحالية، فأعد False. وإذا عُثر على جميع الحروف، فأعد node.is_end — وتكون True فقط إذا انتهت كلمة هنا بالضبط، وليس إذا كانت هذه مجرد بادئة. ويُعد هذا الفرق بين «وجود بادئة» و«وجود كلمة مطابقة تمامًا» مهمًا للغاية، وكثيرًا ما يُختبر.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_end # must be a complete word
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False (app not inserted)
print(t.search('orange')) # Falsestarts_with (البحث عن بادئة)
تتحقق الدالة starts_with مما إذا كانت أي كلمة مُدرجة تبدأ بالبادئة المعطاة. وهي تتبع المسار نفسه المستخدم في البحث، لكنها بدلًا من التحقق من is_end تعيد True فور النجاح في تتبّع جميع حروف البادئة، ما يعني أن مسار البادئة موجود في Trie.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return False
node = node.children[c]
return True # prefix path exists
t = Trie()
t.insert('apple')
print(t.starts_with('app')) # True
print(t.starts_with('ape')) # False
print(t.search('app')) # False (not inserted)التعقيد الزمني والمكاني
تستغرق كل عملية في Trie، وهي insert وsearch وstarts_with، زمنًا قدره O(m)، حيث m هو طول الكلمة، إذ نتتبّع بحد أقصى m عقد. أما المساحة فتعقيدها O(ALPHABET_SIZE × N × M)، حيث N هو عدد الكلمات وM هو متوسط طول الكلمة. عمليًا، تقلل البادئات المشتركة المساحة بدرجة كبيرة. ويستخدم قاموس children المعتمد على hash map مساحة أقل من مصفوفة ثابتة من 26 خانة في Tries قليلة الكثافة، مقابل تكلفة ثابتة أعلى قليلًا لكل عملية بحث.
استخدام مصفوفة بدلًا من Dict
للحروف الإنجليزية الصغيرة فقط، استخدم مصفوفة ثابتة الحجم children = [None] * 26 مع الفهرس ord(c) - ord('a'). فهذا أسرع، إذ يوفر بحثًا عن الابن بتعقيد O(1) مقارنةً بـ hash map، كما يوفّر تخطيطًا متوقعًا للذاكرة. استخدم إصدار dict عندما تكون مجموعة المحارف كبيرة أو غير معروفة، مثل Unicode، واستخدم إصدار المصفوفة في مسائل المسابقات التي تقتصر على الحروف الإنجليزية الصغيرة.
class TrieNodeArray:
def __init__(self):
self.children = [None] * 26
self.is_end = False
class TrieArray:
def __init__(self):
self.root = TrieNodeArray()
def insert(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = TrieNodeArray()
node = node.children[idx]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None: return False
node = node.children[idx]
return node.is_end
t = TrieArray()
t.insert('cat')
print(t.search('cat')) # True
print(t.search('car')) # Falseعملية الحذف
يجب أن تتعامل عملية الحذف من Trie مع ثلاث حالات: (1) الكلمة غير موجودة — لا تفعل شيئًا؛ (2) الكلمة موجودة لكنها بادئة لكلمة أخرى — ألغِ ضبط is_end فقط؛ (3) الكلمة موجودة وليست بادئة — احذف العقد من الأسفل إلى الأعلى، وتوقف عندما تكون للعقدة أبناء آخرون أو تكون نهاية كلمة أخرى. نادرًا ما يُختبر الحذف في المقابلات، لكنه مفهوم جيد ينبغي معرفته.
عدّ الكلمات ذات البادئة
أضف إلى كل عقدة حقل count، وزِد قيمته عند كل مرور أثناء الإدراج. لعدّ الكلمات التي تبدأ ببادئة معيّنة، تتبّع المسار حتى عقدة نهاية البادئة ثم أعد قيمة count الخاصة بها. يتيح ذلك إجراء استعلامات الإكمال التلقائي بتعقيد O(m) دون تتبّع جميع الأبناء، وهو امتداد مفيد لأنظمة الإكمال التلقائي الواقعية.
class TrieNodeCount:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0 # words passing through this node
class TrieCount:
def __init__(self):
self.root = TrieNodeCount()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNodeCount()
node = node.children[c]
node.count += 1 # increment on each level
node.is_end = True
def count_with_prefix(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return 0
node = node.children[c]
return node.count
t = TrieCount()
for w in ['apple','app','application','apply']:
t.insert(w)
print(t.count_with_prefix('app')) # 4
print(t.count_with_prefix('appl')) # 3مقارنة Trie وHash Map
يمكن لـhash map تنفيذ بحث عن تطابق تام بمتوسط زمن O(m)، لكنه لا يستطيع الإجابة بكفاءة عن استعلامات البادئات، إذ يتطلب ذلك فحص جميع المفاتيح. أما Trie فتجيب عن استعلامات البادئات في زمن O(p)، حيث p هو طول البادئة، وتجمع الكلمات طبيعيًا بحسب بادئاتها المشتركة، ولا تحتاج إلى hashing. استخدم Trie عند الحاجة إلى: استعلامات بادئات متكررة، أو إكمال تلقائي، أو تدقيق إملائي. واستخدم hash map عند الحاجة إلى عمليات بحث عن تطابق تام فقط.
Tries في الأنظمة الواقعية
تشمل استخدامات Trie الواقعية: الإكمال التلقائي، مثل اقتراحات بحث Google، وأدوات التدقيق الإملائي، للعثور على الكلمات الأقرب تطابقًا، وتوجيه IP، لمطابقة أطول بادئة في الموجّهات، والنص التنبؤي T9، لإزالة الالتباس بين الحروف، ومحللات DNS، للبحث الهرمي عن أسماء النطاقات. في كل حالة، تجعل المفاضلة بين O(m) لكل عملية وO(ALPHABET × nodes) من المساحة Trie أداة مناسبة للبحث السريع المدرك للبادئات على نطاق واسع.
تحقق سريع
اختبر مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep الواردة في هذا الدرس.
مراجعة الدرس
في هذا الدرس تعلّمتم: أن TrieNode تحتوي على قاموس children وقيمة منطقية is_end، وأن insert تتتبّع الحروف حرفًا حرفًا، وتنشئ العقد حسب الحاجة، وتضبط is_end في النهاية، وأن search تتحقق من is_end، بينما تتحقق starts_with فقط من وجود مسار البادئة. بعد ذلك سنضيف الإكمال التلقائي المعتمد على البادئات، ونتناول الدالة starts_with بمزيد من التفصيل.
الأسئلة الشائعة
هل درس «الفئة TrieNode: الإدراج والبحث» مجاني؟
نعم — نص درس «الفئة TrieNode: الإدراج والبحث» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة DSA Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة DSA Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «الفئة TrieNode: الإدراج والبحث»؟
أنشئ TrieNode مع قاموس children وعلامة is_end، ونفّذ insert وexact-search، وحلّل الزمن O(m) لكل عملية، حيث m هو طول الكلمة. تتمرن على DSA Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ DSA Interview Prep؟
لا تُشترط خبرة سابقة. DSA Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «الفئة TrieNode: الإدراج والبحث»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس DSA Interview Prep هذا؟
نعم. كل درس في DSA Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- الفئة TrieNode: الإدراج والبحث
- البحث عن البادئات وStarts-With
- البحث باستخدام الرموز البديلة والتعبيرات النمطية في Trie
- البحث عن الكلمات II: Trie والتراجع على شبكة