شجرة البادئات

من موسوعة حسوب
اذهب إلى التنقل اذهب إلى البحث

شجرة البادئات (Prefix tree وتعرف أيضًا بالشجرة الرقمية digital tree والتراي Trie) هي بنية معطيات فعالة لاسترجاع المعلومات Information reTrieval data structur. تساعد شجرة البادئات على تقليص التعقيد الزمني لعمليات البحث إلى حدود معقولة، فإن خُزّنت مجموعة من المفاتيح في شجرة بحث ثنائية متوازنة فإن عملية البحث ستستغرق M*logN من الوقت وتمثّل M طول أطول سلسلة نصية، وN عدد المفاتيح الموجودة في الشجرة. ولكن يمكن البحث عن المفاتيح في شجرة البادئات بتعقيد زمني قدره O(M)‎، ولكن تأتي هذه السرعة على حساب مساحة التخزين.

تبدأ شجرة البيانات بعقدة الجذر والتي تكون فارغة، ويتفرع عن هذه العقدة مجموعة من العقد التي تمثّل كل واحدة منها حرفًا من حروف الهجاء، ويتفرّع عن هذه العقد بدورها مجموعة أخرى من العقد التي تمثّل كل واحدة حرفًا من حروف الهجاء. يجب أن توسم آخر عقدة في كل مفتاح كعقدة نهاية الكلمة.

تمثّل كل عقدة بنوية (وتسمّى كذلك بالمفتاح Key) في الشجرة مصفوفة من المؤشرات pointers (أو الإشارات references) إلى المستوى التالي من العقد في شجرة البادئات، ويؤدي الحرف المفتاحي دور الفهرس في المصفوفة البنوية.

عملية الإدراج

يمكن إجراء عمليتين على شجرة البادئات وهما عملية الإدراج وعملية البحث.

وسواء أكان المفتاح المراد إنشاؤه جديدًا أم كان امتدادًا لمفتاحٍ موجود أصلًا، فيجب إنشاء بقية العقد الخاصة بذلك المفتاح، ووسم آخر عقدة منها بوسم نهاية الكلمة. وإن كان المفتاح المراد إضافته يمثّل بادئة للمفتاح الحالي في شجرة البادئات نكتفي بإضافة وسم نهاية الكلمة إلى العقدة الأخيرة فقط، ويمثّل طول المفتاح عمق شجرة البادئات.

عملية البحث

عملية البحث مشابهة لعملية الإدراج، ولكن الفرق هو في إجراء مقارنة بين الأحرف ثم الانتقال نزولًا في شجرة البادئات، وتتوقف عملية البحث عند الوصول إلى نهاية السلسلة النصية أو عند غياب أحد المفاتيح في الشجرة. في الحالة الأولى إن كانت قيمة وسم نهاية الكلمة في العقدة الأخيرة قيمة صحيحة، فهذا يعني أنّ المفتاح موجود في الشجرة، وفي الحالة الثانية تتوقف عملية البحث دون فحص جميع الأحرف الخاصة بالمفتاح المعني، وذلك لأنّه غير موجود في شجرة البادئات.

يعرض الشكل التالي مثالًا عن شجرة البادئات المستخدمة في الأمثلة البرمجية التي سترد لاحقًا: 

                       root
                    /   \    \
                    t   a     b
                    |   |     |
                    h   n     y
                    |   |  \  |
                    e   s  y  e
                 /  |   |
                 i  r   w
                 |  |   |
                 r  e   e
                        |
                        r

يلاحظ أنّ كل حرف في شجرة البادئات يمثّل عقدة فيها، فالجذر عقدة تمتلك عقدًا بنوية بعدد أحرف الهجاء الإنكليزية، ثلاثٌ منها تحتوي على قيم هي a و b و t والباقي تحمل القيمة NULL. وكل عقدة من هذه العقد بدورها تمتلك عقدًا بنوية بعدد أحرف الهجاء، فالعقدة a مثلًا تمتلك عقدة بنوية واحدة قيمتها n أما بقية العقد فتحمل القيمة NULL.

أمثلة برمجية

تعرض الأمثلة التالية طريقة إنشاء أشجار البادئات وإضافة العناصر والبحث عنها، وذلك في عدد من لغات البرمجة:

  • C++‎:
#include <bits/stdc++.h> 
using namespace std; 

const int ALPHABET_SIZE = 26; 

// عقدة في شجرة البادئات
struct TrieNode 
{ 
	struct TrieNode *children[ALPHABET_SIZE]; 

	// وسم نهاية الكلمة
	// تكون قيمته صحيحة إن مثّلت العقدة نهاية الكلمة
	bool isEndOfWord; 
}; 

// تعيد هذه البنية عقدة جديدة في شجرة البادئات 
// NULL تأخذ القيمة الابتدائية
struct TrieNode *getNode(void) 
{ 
	struct TrieNode *pNode = new TrieNode; 

	pNode->isEndOfWord = false; 

	for (int i = 0; i < ALPHABET_SIZE; i++) 
		pNode->children[i] = NULL; 

	return pNode; 
} 

// إن لم يكن المفتاح المراد إضافته موجودًا في الشجرة فإنه يضاف إليها
// وإن كان المفتاح بادئة لإحدى العقد في الشجرة
// فإنّه يوسم بوسم نهاية الكلمة فقط
void insert(struct TrieNode *root, string key) 
{ 
	struct TrieNode *pCrawl = root; 

	for (int i = 0; i < key.length(); i++) 
	{ 
		int index = key[i] - 'a'; 
		if (!pCrawl->children[index]) 
			pCrawl->children[index] = getNode(); 

		pCrawl = pCrawl->children[index]; 
	} 

	// وسم العقدة الأخيرة كعقدة ورقية
	pCrawl->isEndOfWord = true; 
} 

// تعيد الدالة قيمة صحيحة إن كان المفتاح المعطى موجودًا في شجرة البيانات
// وتعيد قيمة خاطئة إن لم يكن موجودًا فيها
bool search(struct TrieNode *root, string key) 
{ 
	struct TrieNode *pCrawl = root; 

	for (int i = 0; i < key.length(); i++) 
	{ 
		int index = key[i] - 'a'; 
		if (!pCrawl->children[index]) 
			return false; 

		pCrawl = pCrawl->children[index]; 
	} 

	return (pCrawl != NULL && pCrawl->isEndOfWord); 
} 

// اختبار الدوال السابقة
int main() 
{ 
	// المفاتيح المدخلة
	// تستخدم هذه المفاتيح الحروف الأبجدية الإنكليزية الصغيرة فقط
	string keys[] = {"the", "a", "there", 
					"answer", "any", "by", 
					"bye", "their" }; 
	int n = sizeof(keys)/sizeof(keys[0]); 

	struct TrieNode *root = getNode(); 

	// بناء شجرة البادئات 
	for (int i = 0; i < n; i++) 
		insert(root, keys[i]); 

	// البحث عن مفاتيح مختلفة
	search(root, "the")? cout << "Yes\n" : 
						cout << "No\n"; 
	search(root, "these")? cout << "Yes\n" : 
						cout << "No\n"; 
	return 0; 
}
  • بايثون:
class TrieNode: 
	
	# صنف يمثّل عقدة في شجرة البادئات
	def __init__(self): 
		self.children = [None]*26

		# وسم نهاية الكلمة
		# تكون قيمته صحيحة إن مثّلت العقدة نهاية الكلمة 
		self.isEndOfWord = False

# صنف يمثّل شجرة البادئات
class Trie: 
	
	def __init__(self): 
		self.root = self.getNode() 

    # يعيد التابع عقدة جديدة في شجرة البادئات
    # NULL تأخذ القيمة الابتدائية
	def getNode(self): 
		return TrieNode() 

	# يحوّل التابع الحرف المعطى إلى فهرس
	# يستخدم التابع الحروف الأبجدية الإنكليزية الصغيرة فقط
	def _charToIndex(self,ch):		
		return ord(ch)-ord('a') 

    # إن لم يكن المفتاح المراد إضافته موجودًا في الشجرة فإنه يضاف إليها
    # وإن كان المفتاح بادئة لإحدى العقد في الشجرة
    # فإنّه يوسم بوسم نهاية الكلمة فقط
	def insert(self,key): 
		pCrawl = self.root 
		length = len(key) 
		for level in range(length): 
			index = self._charToIndex(key[level]) 

			# إن لم يكن الحرف الحالي موجودًا
			if not pCrawl.children[index]: 
				pCrawl.children[index] = self.getNode() 
			pCrawl = pCrawl.children[index] 

		# وسم العقدة الأخيرة كعقدة ورقية
		pCrawl.isEndOfWord = True

# تعيد الدالة قيمة صحيحة إن كان المفتاح المعطى موجودًا في شجرة البيانات
# وتعيد قيمة خاطئة إن لم يكن موجودًا فيها
	def search(self, key): 
		pCrawl = self.root 
		length = len(key) 
		for level in range(length): 
			index = self._charToIndex(key[level]) 
			if not pCrawl.children[index]: 
				return False
			pCrawl = pCrawl.children[index] 

		return pCrawl != None and pCrawl.isEndOfWord 

# اختبار الدوال السابقة
if __name__ == '__main__':  

	# المفاتيح المدخلة
	# تستخدم هذه المفاتيح الحروف الأبجدية الإنكليزية الصغيرة فقط 
	keys = ["the","a","there","anaswe","any", 
			"by","their"] 
	output = ["Not present in trie", 
			"Present in trie"] 

	t = Trie() 

	# بناء شجرة البادئات
	for key in keys: 
		t.insert(key) 

	# البحث عن مفاتيح مختلفة 
	print("{} ---- {}".format("the",output[t.search("the")])) 
	print("{} ---- {}".format("these",output[t.search("these")])) 
	print("{} ---- {}".format("their",output[t.search("their")])) 
	print("{} ---- {}".format("thaw",output[t.search("thaw")]))
  • جافا:
public class Trie { 
	
	// عدد الرموز المستخدمة في شجرة البادئات
	static final int ALPHABET_SIZE = 26; 
	
	// عقدة في شجرة البادئات 
	static class TrieNode 
	{ 
		TrieNode[] children = new TrieNode[ALPHABET_SIZE]; 
	
    	// وسم نهاية الكلمة
    	// تكون قيمته صحيحة إن مثّلت العقدة نهاية الكلمة 
		boolean isEndOfWord; 
		
		TrieNode(){ 
			isEndOfWord = false; 
			for (int i = 0; i < ALPHABET_SIZE; i++) 
				children[i] = null; 
		} 
	}; 
	
	static TrieNode root; 
	
    // إن لم يكن المفتاح المراد إضافته موجودًا في الشجرة فإنه يضاف إليها
    // وإن كان المفتاح بادئة لإحدى العقد في الشجرة
    // فإنّه يوسم بوسم نهاية الكلمة فقط 
	static void insert(String key) 
	{ 
		int level; 
		int length = key.length(); 
		int index; 
	
		TrieNode pCrawl = root; 
	
		for (level = 0; level < length; level++) 
		{ 
			index = key.charAt(level) - 'a'; 
			if (pCrawl.children[index] == null) 
				pCrawl.children[index] = new TrieNode(); 
	
			pCrawl = pCrawl.children[index]; 
		} 
	
		// وسم العقدة الأخيرة كعقدة ورقية 
		pCrawl.isEndOfWord = true; 
	} 
	
	// يعيد التابع قيمة صحيحة إن كان المفتاح المعطى موجودًا في شجرة البيانات
    // ويعيد قيمة خاطئة إن لم يكن موجودًا فيها
	static boolean search(String key) 
	{ 
		int level; 
		int length = key.length(); 
		int index; 
		TrieNode pCrawl = root; 
	
		for (level = 0; level < length; level++) 
		{ 
			index = key.charAt(level) - 'a'; 
	
			if (pCrawl.children[index] == null) 
				return false; 
	
			pCrawl = pCrawl.children[index]; 
		} 
	
		return (pCrawl != null && pCrawl.isEndOfWord); 
	} 
	
	// اختبار التوابع السابقة
	public static void main(String args[]) 
	{ 
		// المفاتيح المدخلة
		// تستخدم هذه المفاتيح الحروف الأبجدية الإنكليزية الصغيرة فقط
		String keys[] = {"the", "a", "there", "answer", "any", 
						"by", "bye", "their"}; 
	
		String output[] = {"Not present in trie", "Present in trie"}; 
	
	
		root = new TrieNode(); 
	
		// بناء شجرة البادئات 
		int i; 
		for (i = 0; i < keys.length ; i++) 
			insert(keys[i]); 
	
		// البحث عن مفاتيح مختلفة
		if(search("the") == true) 
			System.out.println("the --- " + output[1]); 
		else System.out.println("the --- " + output[0]); 
		
		if(search("these") == true) 
			System.out.println("these --- " + output[1]); 
		else System.out.println("these --- " + output[0]); 
		
		if(search("their") == true) 
			System.out.println("their --- " + output[1]); 
		else System.out.println("their --- " + output[0]); 
		
		if(search("thaw") == true) 
			System.out.println("thaw --- " + output[1]); 
		else System.out.println("thaw --- " + output[0]); 
		
	} 
}

تعطي الشيفرات السابقة المخرجات التالية: 

the --- Present in trie
these --- Not present in trie
their --- Present in trie
thaw --- Not present in trie

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

تستغرق عمليتا الإدراج والبحث زمنًا قدره O(key_length)‎ ولكنّ شجرة البادئات تحتاج إلى مساحة في الذاكرة قدرها O(ALPHABET_SIZE * key_length * N)‎ وتمثّل ALPHABET_SIZE عدد الحروف المستخدمة، وkey_length طول المفتاح وN عدد المفاتيح في الشجرة.

حذف المفتاح

يحذف المفتاح من شجرة البادئات باستخدام التعاود ومن أسفل الشجرة إلى أعلاها، وهناك عدد من الحالات التي يمكن مواجهتها عند حذف المفتاح من شجرة البادئات:

  1. قد لا يكون المفتاح المراد حذفه موجودًا في شجرة البادئات، ويجب حينئذٍ أن لا تجري عملية الحذف أي تعديل على الشجرة.
  2. قد يكون المفتاح المراد حذفه فريدًا (أي لا يحتوي أي جزء من المفتاح على مفتاح آخر (بادئة) أو لا يكون المفتاح نفسه بادئة لمفتاح آخر في الشجرة)، وحينئذٍ تُحذف جميع العقد.
  3. قد يكون المفتاح المراد حذفه مفتاح بادئة لمفتاح طويل آخر في الشجرة، وحينئذٍ يزال الوسم من العقدة الورقية.
  4. قد يكون المفتاح موجودًا في الشجرة، ويمتلك على الأقل مفتاحًا آخر كمفتاح بادئة، وحينئذٍ تُحذف العقد من نهاية المفتاح وصولًا إلى أول عقدة ورقية لأطول مفتاح بادئة.

يعرض المثال التالي طريقة تنفيذ عملية حذف مفتاح من شجرة البادئات في لغة C++‎: 

#include <bits/stdc++.h> 
using namespace std; 

const int ALPHABET_SIZE = 26; 

// عقدة في شجرة البادئات
struct TrieNode { 
	struct TrieNode* children[ALPHABET_SIZE]; 

	// وسم نهاية الكلمة 
	// تكون قيمته صحيحة إن مثّلت العقدة نهاية الكلمة
	bool isEndOfWord; 
}; 

// تعيد هذه البنية عقدة جديدة في شجرة البادئات
// NULL تأخذ القيمة الابتدائية
struct TrieNode* getNode(void) 
{ 
	struct TrieNode* pNode = new TrieNode; 

	pNode->isEndOfWord = false; 

	for (int i = 0; i < ALPHABET_SIZE; i++) 
		pNode->children[i] = NULL; 

	return pNode; 
} 

// إن لم يكن المفتاح المراد إضافته موجودًا في الشجرة فإنه يضاف إليها
// وإن كان المفتاح بادئة لإحدى العقد في الشجرة
// فإنّه يوسم بوسم نهاية الكلمة فقط 
void insert(struct TrieNode* root, string key) 
{ 
	struct TrieNode* pCrawl = root; 

	for (int i = 0; i < key.length(); i++) { 
		int index = key[i] - 'a'; 
		if (!pCrawl->children[index]) 
			pCrawl->children[index] = getNode(); 

		pCrawl = pCrawl->children[index]; 
	} 

	// وسم العقدة الأخيرة كعقدة ورقية 
	pCrawl->isEndOfWord = true; 
} 

// تعيد الدالة قيمة صحيحة إن كان المفتاح المعطى موجودًا في شجرة البيانات 
// وتعيد قيمة خاطئة إن لم يكن موجودًا فيها
bool search(struct TrieNode* root, string key) 
{ 
	struct TrieNode* pCrawl = root; 

	for (int i = 0; i < key.length(); i++) { 
		int index = key[i] - 'a'; 
		if (!pCrawl->children[index]) 
			return false; 

		pCrawl = pCrawl->children[index]; 
	} 

	return (pCrawl != NULL && pCrawl->isEndOfWord); 
} 

// تعيد الدالة قيمة صحيحة إن كان المفتاح المعطى موجودًا في شجرة البيانات
// وتعيد قيمة خاطئة إن لم يكن موجودًا فيها
bool isEmpty(TrieNode* root) 
{ 
	for (int i = 0; i < ALPHABET_SIZE; i++) 
		if (root->children[i]) 
			return false; 
	return true; 
} 

// دالة تعاودية لحذف المفتاح المعطى من شجرة البادئات
TrieNode* remove(TrieNode* root, string key, int depth = 0) 
{ 
	// إن كانت الشجرة فارغة 
	if (!root) 
		return NULL; 

	// إن جرت معالجة آخر حرف في المفتاح
	if (depth == key.size()) { 

		// لن تمثل هذه العقدة نهاية الكلمة
		// بعد حذف المفتاح المعطى
		if (root->isEndOfWord) 
			root->isEndOfWord = false; 

		// إن لم يكن المفتاح المعطى بادئة لأي كلمة أخرى
		if (isEmpty(root)) { 
			delete (root); 
			root = NULL; 
		} 

		return root; 
	} 

    // إن لم يكن الحرف الأخير تستدعى الدالة تعاوديًا على العقد البنوية
    // ASCII التي يمكن الحصول عليها باستخدام قيمة
	int index = key[depth] - 'a'; 
	root->children[index] = 
		remove(root->children[index], key, depth + 1); 

	// إن لم يمتلك جذر الشجرة أي عقد بنوية 
	// ولم يكن المفتاح نهاية كلمة أخرى
	if (isEmpty(root) && root->isEndOfWord == false) { 
		delete (root); 
		root = NULL; 
	} 

	return root; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	// المفاتيح المدخلة
	// تستخدم هذه المفاتيح الحروف الأبجدية الإنكليزية الصغيرة فقط 
	string keys[] = { "the", "a", "there", 
					"answer", "any", "by", 
					"bye", "their", "hero", "heroplane" }; 
	int n = sizeof(keys) / sizeof(keys[0]); 

	struct TrieNode* root = getNode(); 

	// بناء شجرة البادئات 
	for (int i = 0; i < n; i++) 
		insert(root, keys[i]); 

	// البحث عن مفاتيح مختلفة 
	search(root, "the") ? cout << "Yes\n" : cout << "No\n"; 
	search(root, "these") ? cout << "Yes\n" : cout << "No\n"; 

	remove(root, "heroplane"); 
	search(root, "hero") ? cout << "Yes\n" : cout << "No\n"; 
	return 0; 
}

تعطي الشيفرات السابقة المخرجات التالية: 

Yes
No
Yes

الإكمال التلقائي باستخدام شجرة البادئات

تقدّم أنظمة التشغيل والبرامج المختلفة خاصية الإكمال التلقائي Auto-complete، إذ يُدخل المستخدمة جزءًا من الكلمة التي يريد البحث عنها فيعطيه النظام أو البرنامج بعض الاقتراحات لإكمال الكلمة التي أدخلها تلقائيًا وذلك بالاستناد إلى مجموعة من السلاسلة النصية المخزّنة في شجرة البادئات. وسنفترض في هذا المثال أنّ الشجرة البادئة تخزّن عمليات البحث السابقة التي أجراها المستخدم.

إن خزّنت شجرة البادئات -على سبيل المثال- الكلمات ‎{"abc", "abcd", "aa", "abbbaba"}‎ وأدخل المستخدم الحرفية "ab" فإنّ الاقتراحات التي ستظهر له هي: ‎{"abc", "abcd", "abbbaba"}‎.

تجري عملية البحث عن الكلمات المطلوبة في شجرة البادئات باتباع الخطوات التالية:

  1. البحث عن العبارة التي أدخلها المستخدم باستخدام خوارزمية البحث في شجرة البادئات.
  2. إن لم تعثر خوارزمية البحث عن أيّ بادئة للعبارة المدخلة، تعيد القيمة ‎1-.
  3. إن كانت العبارة المدخلة موجودة وكانت نهاية كلمة في شجرة البادئات، تطبع الخوارزمية تلك العبارة. يمكن التأكد من ذلك بالتحقق من أنّ آخر عقدة مطابقة تمتلك وسم نهاية الكلمة.
  4. إن لم تمتلك آخر عقدة مطابقة أي عقد بنوية، تتوقف الخوارزمية عن العمل.
  5. إن لم يتحقق الشرط السابق تطبع الخوارزمية تعاوديًا جميع العقد الموجودة تحت الشجرة المتفرّعة عن آخر عقدة مطابقة.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

  • C++‎:
#include<bits/stdc++.h> 
using namespace std; 

// عدد الأحرف الهجائية المستخدمة في شجرة البادئات
#define ALPHABET_SIZE (26) 

// تحوّل الدالة الحرف المعطى إلى فهرس 
// تستخدم الدالة الحروف الأبجدية الإنكليزية الصغيرة فقط 
#define CHAR_TO_INDEX(c) ((int)c - (int)'a') 

// عقدة في شجرة البادئات 
struct TrieNode 
{ 
	struct TrieNode *children[ALPHABET_SIZE]; 

	// وسم نهاية الكلمة 
	// تكون قيمته صحيحة إن مثّلت العقدة نهاية الكلمة 
	bool isWordEnd; 
}; 

// تعيد هذه البنية عقدة جديدة في شجرة البادئات
// NULL تأخذ القيمة الابتدائية
struct TrieNode *getNode(void) 
{ 
	struct TrieNode *pNode = new TrieNode; 
	pNode->isWordEnd = false; 

	for (int i = 0; i < ALPHABET_SIZE; i++) 
		pNode->children[i] = NULL; 

	return pNode; 
} 

// إن لم يكن المفتاح المراد إضافته موجودًا في الشجرة فإنه يضاف إليها 
// وإن كان المفتاح بادئة لإحدى العقد في الشجرة
// فإنّه يوسم بوسم نهاية الكلمة فقط
void insert(struct TrieNode *root, const string key) 
{ 
	struct TrieNode *pCrawl = root; 

	for (int level = 0; level < key.length(); level++) 
	{ 
		int index = CHAR_TO_INDEX(key[level]); 
		if (!pCrawl->children[index]) 
			pCrawl->children[index] = getNode(); 

		pCrawl = pCrawl->children[index]; 
	} 

	// وسم العقدة الأخيرة كعقدة ورقية 
	pCrawl->isWordEnd = true; 
} 

// تعيد الدالة قيمة صحيحة إن كان المفتاح المعطى موجودًا في شجرة البيانات
// وتعيد قيمة خاطئة إن لم يكن موجودًا فيها
bool search(struct TrieNode *root, const string key) 
{ 
	int length = key.length(); 
	struct TrieNode *pCrawl = root; 
	for (int level = 0; level < length; level++) 
	{ 
		int index = CHAR_TO_INDEX(key[level]); 

		if (!pCrawl->children[index]) 
			return false; 

		pCrawl = pCrawl->children[index]; 
	} 

	return (pCrawl != NULL && pCrawl->isWordEnd); 
} 

// تعيد الدالة صفرًا إن امتلكت العقدة الحالية عقدًا بنوية
// NULL وإن حملت جميع العقد البنوية القيمة 
// تعيد الدالة القيمة 1
bool isLastNode(struct TrieNode* root) 
{ 
	for (int i = 0; i < ALPHABET_SIZE; i++) 
		if (root->children[i]) 
			return 0; 
	return 1; 
} 

// دالة تعاوية لطباعة الاقتراحات التلقائية
// للعقدة المعطاة
void suggestionsRec(struct TrieNode* root, string currPrefix) 
{ 
	// إن عثرت الدالة على سلسلة نصية في شجرة البادئات تمتلك البادئة المعطاة
	if (root->isWordEnd) 
	{ 
		cout << currPrefix; 
		cout << endl; 
	} 

	// NULL إن كانت جميع العقد البنوية تشير إلى القيمة 
	if (isLastNode(root)) 
		return; 

	for (int i = 0; i < ALPHABET_SIZE; i++) 
	{ 
		if (root->children[i]) 
		{ 
			// currPrefix إلحاق الحرف الحالي بالسلسلة النصية 
			currPrefix.push_back(97 + i); 

			// تنفيذ الدالة تعاوديًا على بقية الحروف
			suggestionsRec(root->children[i], currPrefix); 
		} 
	} 
} 

// طباعة الاقتراحات الخاصة بعبارة البحث المدخلة //
int printAutoSuggestions(TrieNode* root, const string query) 
{ 
	struct TrieNode* pCrawl = root; 

	// التحقق من وجود البادئة والبحث عن العقدة
	// (في المستوى الأخير) والتي تمتلك الحرف الأخير
	// من السلسلة النصية المعطاة
	int level; 
	int n = query.length(); 
	for (level = 0; level < n; level++) 
	{ 
		int index = CHAR_TO_INDEX(query[level]); 

		// إن لم تمتلك أي سلسلة نصية في شجرة البادئات هذه البادئة
		if (!pCrawl->children[index]) 
			return 0; 

		pCrawl = pCrawl->children[index]; 
	} 

	// إن كانت البادئة موجودة ككلمة كاملة
	bool isWord = (pCrawl->isWordEnd == true); 

	// إن لم تمتلك العقدة عقدًا بنوية في الشجرة
	bool isLast = isLastNode(pCrawl); 

	// إن كانت البادئة موجودة ككلمة كاملة
	// ولكن لا توجد شجرة متفرعة من آخر عقدة مطابقة
	if (isWord && isLast) 
	{ 
		cout << query << endl; 
		return -1; 
	} 

	// إن كانت هناك عقد تحت آخر حرف مطابق
	if (!isLast) 
	{ 
		string prefix = query; 
		suggestionsRec(pCrawl, prefix); 
		return 1; 
	} 
} 

// اختبار الدوال السابقة 
int main() 
{ 
	struct TrieNode* root = getNode(); 
	insert(root, "hello"); 
	insert(root, "dog"); 
	insert(root, "hell"); 
	insert(root, "cat"); 
	insert(root, "a"); 
	insert(root, "hel"); 
	insert(root, "help"); 
	insert(root, "helps"); 
	insert(root, "helping"); 
	int comp = printAutoSuggestions(root, "hel"); 

	if (comp == -1) 
		cout << "No other strings found with this prefix\n"; 

	else if (comp == 0) 
		cout << "No string found with this prefix\n"; 

	return 0; 
}
  • بايثون:
class TrieNode(): 
	def __init__(self): 
		
		تهيئة عقدة للشجرة البادئة
		self.children = {} 
		self.last = False

class Trie(): 
	def __init__(self): 
		
		# تهيئة بنية الشجرة البادئة
		self.root = TrieNode() 
		self.word_list = [] 

	def formTrie(self, keys): 
		
		# تشكل هذه الحلقة التكرارية بنية شجرة البادئات
		# باستخدام مجموعة السلاسل النصية المعطاة
		# إن لم تكن هناك شجرة بادئة أصلًا
		# وإلا فإنّها تدمج المفتاح في الشجرة الموجودة
		# عن طريق توسيع بنيتها حسب الحاجة
		for key in keys: 
			self.insert(key) # inserting one key to the trie. 
    # إن لم يكن المفتاح المراد إضافته موجودًا في الشجرة فإنه يضاف إليها 
	def insert(self, key): 
		node = self.root 

		for a in list(key): 
			if not node.children.get(a): 
				node.children[a] = TrieNode() 

			node = node.children[a] 

		node.last = True

	def search(self, key): 
		
		# تعيد الدالة قيمة صحيحة إن كان المفتاح المعطى موجودًا في شجرة البيانات
		# وتعيد قيمة خاطئة إن لم يكن موجودًا فيها returns False. 
		node = self.root 
		found = True

		for a in list(key): 
			if not node.children.get(a): 
				found = False
				break

			node = node.children[a] 

		return node and node.last and found 
    
    # يستخدم هذا التابع للتنقل بين عقد شجرة البادئات
    # ويعيد كلمة كاملة
	def suggestionsRec(self, node, word): 
		
		if node.last: 
			self.word_list.append(word) 

		for a,n in node.children.items(): 
			self.suggestionsRec(n, word + a) 
    
    # يعيد التابع جميع الكلمات الموجودة في شجرة البادئات والتي تشترك في البادئة المعطاة
    # وهذا يعني تقديم جميع الاقتراحات لخاصية الإكمال التلقائي
	def printAutoSuggestions(self, key): 
		node = self.root 
		not_found = False
		temp_word = '' 

		for a in list(key): 
			if not node.children.get(a): 
				not_found = True
				break

			temp_word += a 
			node = node.children[a] 

		if not_found: 
			return 0
		elif node.last and not node.children: 
			return -1

		self.suggestionsRec(node, temp_word) 

		for s in self.word_list: 
			print(s) 
		return 1

# اختبار الدوال السابقة 
keys = ["hello", "dog", "hell", "cat", "a", 
		"hel", "help", "helps", "helping"] # تستخدم هذه الكلمات لتشكيل بنية شجرة البادئات 
key = "hel" # المفتاح المدخل من قبل المستخدم
status = ["Not found", "Found"] 

# إنشاء كائن شجرة البادئات
t = Trie() 

# إنشاء بنية شجرة البادئات
# باستخدام مجموعة السلاسل النصية المعطاة
t.formTrie(keys) 

# إكمال المفتاح المعطى تلقائيًا
# باستخدام شجرة البادئات التي تم إنشاؤها
comp = t.printAutoSuggestions(key) 

if comp == -1: 
	print("No other strings found with this prefix\n") 
elif comp == 0: 
	print("No string found with this prefix\n")

مصادر

مجلوبة من "https://wiki.hsoub.com/index.php?title=Algorithms/tries&oldid=29582"