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

شجرة البادئات (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 عدد المفاتيح في الشجرة.

حذف المفتاح

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

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

يعرض المثال التالي طريقة تنفيذ عملية حذف مفتاح من شجرة البادئات في لغة 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; 
}