درخت پیشوندی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
يك ترای با كليدهای in , i, ten, ted, tea, to, A و inn

در علم رایانه ترای یا درخت پیشوندی یک داده‌ساختار درختی است که برای آرایه‌های شرکت‌پذیری استفاده می‌شود که کلیدهای آن معمولاً رشته می‌باشند. برخلاف یک درخت دودویی جستجو در این درخت هیچ گرهی، کلیدی را که توسط آن گره مشخص می‌شود ذخیره نمی‌کند؛ در عوض، موقعیت آن در درخت نشان دهنده کلید مربوط به آن است. تمام فرزندان یک گره پیشوند مشترکی دارند که این پیشوند در گره مربوطه ذخیره می‌شود. گره ریشه نیز یک رشته خالی است. معمولاً همه گره‌ها مشخص کننده کلیدها نیستند. فقط برگها و بعضی از گره‌های داخلی با کلیدها مرتبط می‌شوند. گره‌های حاوی کلید به نحوی علامتگذاری می‌شوند تا تمام کلیدها مشخص شوند.

البته یک ترای الزاماً شامل رشته‌های کاراکتری نمی‌باشد، بلکه حتی برای جایگشتهای عددی و مواردی از این قبیل هم می‌توان از ترای استفاده کرد.

مزایای ترای نسبت به درخت دودویی جستجو[ویرایش]

جستجوی کلیدها در ترای سریعتر است و از مرتبه طول کلید می‌باشد. اما در یک درخت دودویی جستجو با تعداد گره n باید به طور متوسط (O(nlgn مقایسه انجام داد که تعداد مقایسه‌ها در بدترین حالت به n نزدیک می‌شود.

ترای زمانی که شامل تعداد زیادی از رشته‌های کوچک باشد، فضای کمتری نسبت به درخت دودویی جستجو برای ذخیره اشغال می‌کند.

کاربردها[ویرایش]

جایگزینی جدول درهم[ویرایش]

ترای می‌تواند به عنوان جایگزین جدول درهم نیز استفاده شود.

مزایا:

۱- جستجوی داده‌ها در ترای سریعتر است و در بدترین حالت از (O(m می‌باشد. اما در جدول درهم در شرایط بد این کار از (O(n می‌باشد.

۲- در ترای تصادم وجود ندارد.

۳- در ترای نیازی به توابع درهم سازی و یا تغییر این توابع نیست.

۴- ترای می‌تواند ترتیب الفبایی داشته باشد.

معایب:

ترای در مواردی مکن است کندتر باشد. مخصوصا در جاهایی که داده‌ها مستقیماً از دیسک سخت یا سایر حافظه‌های جانبی در دسترس هستند و سرعت دسترسی تصادفی در آنها به مراتب کمتر از حافظه اصلی است.

نمایش فرهنگ لغت[ویرایش]

استفاده رایج ترای در ذخیره سازی فرهنگ لغت است. برنامه‌های فرهنگ لغت از توانایی و سرعت بالای ترای در جستجو، درج و حذف کلیدها بهره می‌برند.

مرتب سازی[ویرایش]

مرتب سازی واژه نگاری یک مجموعه از کلیدها بوسیله الگوریتمی که از ترای استفاده می‌کند به این ترتیب است:

- درج تمام کلیدها در ترای

- خروج تمام کلیدها بوسیله پیمایش پیش ترتیبی

الگوریتم[ویرایش]

یک برنامه‌ی ساده و با رویکرد استفاده از توابع بازگشتی به زبان سی++ برای ذخیره‌ی اطلاعات در یک درخت ترای و دسترسی و جست‌و‌جو در این ساختمان داده‌ها در زیر آمده‌است:

#include<iostream>
#include<string>
#define alph 26
using namespace std;
/*	node structure (of course it has 26 chidren) and add and search
 functions are for lower case alphabets	*/
 
struct node
{
	bool value;	//if it's end of word or not
	node* next[alph];	//all alphabet for next digits
	node()	//initialization, the constructor
	{
		this->value= 0;
		for(int i=0; i<alph ; i++)
			next[i]= NULL;	//there is no next digit initialy
	}
};

void add( node* head , string word );
bool search( node* head , string query );

int main()
{
	node* root= new node();
	int n;
	cout << " enter number of words you wanna insert " <<endl;
	cin >> n;
	for(int i=0; i<n; i++)
	{
		cout << "enter word "<<endl;
		string word;
		cin>>word;
		add(root,word);
	}
	cout << " enter number of words you wanna search " <<endl;
	cin >> n;
	for(int i=0; i<n; i++)
	{
		cout << "enter query "<<endl;
		string word;
		cin>>word;
		if(search(root,word))
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	return 0;
}
void add( node* head , string word )
{
	if(word.length()==1)
	{
		if(head->next[word[0]-'a']==NULL)
			head->next[word[0]-'a']= new node();
		//"word-'a'" makes an index alphabet number, 26 more or less of course
		head->next[word[0]-'a']->value = 1;
		return;
	}
	else //if(word.length()>1)
	{
		if(head->next[word[0]-'a']==NULL)
			head->next[word[0]-'a']= new node();
		return add(head->next[word[0]-'a'], word.substr(1,word.length()-1));
	}
}
bool search(node*head,string query)
{
	if(query.length()==1)
	{
		if(head->next[query[0]-'a']==NULL)
			return false;
		else if	(head->next[query[0]-'a']->value)
			return true;
		else return false;
	}
	else
	{
		if(head->next[query[0]-'a']==NULL)
			return false;
		else return search(head->next[query[0]-'a'],query.substr(1,query.length()-1));
	}
}

فشرده سازی ترای[ویرایش]

در حالتی که ترای پایستار باشد و نیازی به حذف و درج بعدی در آن نباشد، می‌توان با ادغام گره‌ها، ترای را فشرده کرد.

نگارخانه[ویرایش]

پیوند به بیرون[ویرایش]

منابع[ویرایش]

  • کتاب CLRS
  • ویکی‌پدیای انگلیسی