الشجرة الرقمية (Trie)

ما هيا الشجرة الرقمية (Trie Data structure) ؟

بعبارات بسيطة Trie هيا هيكلة بيانات تعتمد في عملها على (اجزاء من السلاسل Prefix of string) ويتم استخدامها لتخزين المفاتيح واسترجاعها بكفاءة في مجموعة بيانات من السلاسل (Strings).

التطبيقات 🚀

1. المكمل التلقائي
2. كلمات البحث
3. المدقق الإملائي
4. تاريخ المتصفح

الميزات ⚡

الشجرة الرقمية Trie مميزة لأنها سريعة جدًا. فمثلا عند البحث عن كلمة تبدأ بـ A ، ستقوم بإزالة جميع الكلمات التي لا تبدأ بـ A وإذا كنت تبحث عن كلمة App ستقوم بتقليل الوقت الذي يستغرقه العثور على الكلمة بشكل هائل بدلاً من استخدام Array لحفظ قائمة الكلمات.

مثال تجريبي

تتكون Trie العادية من:

1. Root - هذه نقطة البداية في الشجرة
2. Trie Node - يتم تمثيل كل حرف باستخدام عقدة لها خاصيتان
   1. Child - ستحتوي على قيمة العقدة نفسها والوصل بين العقد التابعة لها
   2. IsEnd - عبارة عن True او False للعقدة الحالية ويعبر هل هذه العقدة تعبر عن نهاية كلمة معينة ام لا.

فيما يلي مثال على Trie تتكون من أربع كلمات (And, All, Bank, Bat) ويظهر هيكل Trie وكيف يمكننا البحث في الشجرة ومعرفة أين هي الكلمات:

مشاكل LeetCode 🔨

لتنفيذ بنية البيانات Trie ، سأستخدم مشكلتين من LeetCode لإظهار كيف يمكننا تنفيذ Trie واستخدامها لحل مشكلة حقيقية.

المشكلة 1: تنفيذ Trie (شجرة البادئة)

تحقق من تفاصيل المشكلة هنا.

متطلبات السؤال:

تنفيذ Trie Class:

• Trie() - تهيئة كائن ل Trie
• void insert(String word) - ادرج الكلمة المدخلة الى ال Trie
• boolean search(String word) - نقوم بأرجاع true اذا كانت الكلمة موجودة في ال Trie و false اذا لا
• boolean startsWith(String prefix) - إرجاع true إذا كان هناك سلسلة word مدرجة مسبقا تحتوي على الprefix prefix و false اذا لم توجد.

خطوات 🪜 الحلول

الخطوة 1: تهيئة TrieNode

لإنشاء Trie أولا ، سنقوم بإنشاء كلاس باسم TrieNode الذي هو تمثيل لعقدة كل حرف و تحمل العقدة ال Value, Children, isEnd:

class TrieNode {
  constructor(child = {}, isEnd = false) {
    this.child = child
    this.isEnd = isEnd
  }
}

بشكل افتراضي ، سيبدأ TrieNode بدون أي children و isEnd سيكون false حتى نقوم بإدراج حروف الكلمات وجعل عقدة الحرف الأخير من الكلمة في ال TrieNode لتكون True.

تصور لشكل الTrieNode أو الشجرة الرقمية :

الخطوة 2: تهيئة شجرة Trie (سلسلة الشجرة):

سيتم بدء كلاس Trie بقائمة تم تعيينها على TrieNode جديدة تمثل الجذر (نقطة البداية).

class Trie {
  constructor() {
    this.list = new TrieNode()
  }
}

تبدء الشجرة الرقمية بالجذر بهذا الشكل:

الخطوة 3: إضافة وظائف Trie:

لدينا ثلاث وظائف نريد إضافتها في كلاس Trie:

// Insert new word to the list
insert(word: string): void {}

// Search for a word in the list
search(word: string): boolean {}

// Search if there is a word that start with specific set of characters.
startsWith(prefix: string): boolean {}

دعنا الآن نوضح كيفية إضافة الكلمات في القائمة واستخدام وظائف البحث للبحث في ال Trie.

إدراج (Insert):

لإدراج كلمة App في قائمتنا ، نحتاج ان نمر على كل الحروف في الكلمة (Loop) وفي كل حرف نتحقق مما إذا كان هناك TrieNode موجود حتى نستطيع استعمال العقدة ونستمر ، أو ننشئ TrieNode جديدًا للحرف المحدد.

خطوات:

• إنشاء متغير node للوصول إلى العقد في القائمة.
• نمر على كل الحروف (Loop) في كلمة App.
• تحقق مما إذا كان الحرف موجودًا في القائمة.
  • إذا لم يكن الحرف موجودًا ، فقم بإنشاء TrieNode
• الدخول في عقدة الحرف التالي.
• قم بتعيين عقدة الحرف الأخير isEnd إلى True.

insert(word: string): void {
	let node = this.list
	for (const char of word) {
		if (!node[char]){
			node[char] = new TrieNode()
		}
		node = node[char]
	}
	node.isEnd = true
}

بحث (Search):

يمكننا اتباع نفس نمط إدراج الكلمة ولكن أثناء البحث علينا التحقق من كل حرف إذا كان هناك TrieNode أم لا وإذا لم يكن هناك يمكننا استرجاع return false على الفور.

خطوات:

• إنشاء متغير node للوصول إلى العقد في القائمة.
• نمر على كل الحروف في الكلمة (Loop).
• تحقق مما إذا كان الحرف موجودًا في القائمة.
  • إذا لم يكن الحرف موجودًا ، فارجع False
• الدخول في عقدة الحرف التالي.
• إرجاع True إذا كان isEnd في عقدة الحرف الأخير هيا True واذا لا نرجع False.

search(word: string): boolean {
  let node = this.list
  for (const char of word) {
   if (!node[char]) return false
   node = node[char]
  }
  return node.isEnd
 }

يبدأ ب (StartsWith):

يمكننا اتباع خطوات دالة Search بالضبط ولكن في النهاية سنعيد True سواء كانت هناك كلمة في نهاية السلسلة او لا.

خطوات:

• إنشاء متغير node للوصول إلى العقد في القائمة.
• نمر على كل الحروف في الكلمة (Loop).
• تحقق مما إذا كان الحرف موجودًا في القائمة.
  • إذا لم يكن الحرف موجودًا ، فارجع False
• الدخول في عقدة الحرف التالي.
• إرجاع True.

 startsWith(prefix: string): boolean {
  let node = this.list
  for (const char of prefix){
    if (!node[char]) return false
    node = node[char]
  }
  return true
 }