نمایش مبدأ برای درخت پیشوندی

[[پرونده:trie example.svg|بندانگشتی|چپ|250px|يك ترای با كليدهای in , i, ten, ted, tea, to, A و inn]]
در [[علم رایانه]] ترای یا '''درخت پیشوندی''' یک [[ساختار داده ها|داده‌ساختار]] [[درخت (ساختار داده)|درختی]] است که برای [[آرایه (رایانه)|آرایه‌های]] شرکت‌پذیری استفاده می‌شود که کلیدهای آن معمولاً [[رشته (علوم رایانه)|رشته]] می‌باشند. برخلاف یک [[درخت جستجوی دودویی|درخت دودویی جستجو]] در این درخت هیچ گرهی، کلیدی را که توسط آن گره مشخص می‌شود ذخیره نمی‌کند؛ در عوض، موقعیت آن در درخت نشان دهنده کلید مربوط به آن است. تمام فرزندان یک گره پیشوند مشترکی دارند که این پیشوند در گره مربوطه ذخیره می‌شود. گره ریشه نیز یک رشته خالی است. معمولاً همه گره‌ها مشخص‌کننده کلیدها نیستند. فقط برگ‌ها و بعضی از گره‌های داخلی با کلیدها مرتبط می‌شوند. گره‌های حاوی کلید به نحوی علامت‌گذاری می‌شوند تا تمام کلیدها مشخص شوند.

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

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

جستجوی کلیدها در ترای سریعتر است و از [[پیچیدگی زمانی|مرتبه]] طول کلید می‌باشد. اما در یک [[درخت جستجوی دودویی|درخت دودویی جستجو]] با تعداد گره n باید <math>\log(n)</math> مقایسه برای پیدا کردن یک عنصر انجام داد.

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

== کاربردها ==

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

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

مزایا:

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

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

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

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

معایب:

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

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

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

=== مرتب سازی ===

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

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

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

== الگوریتم ==

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

<syntaxhighlight lang="c++">
#include<iostream>
#include<string>
#define alph 26
using namespace std;
/*	node structure (of course it has 26 children) 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();
//%22word-%27a%27%22 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));
}
}
</syntaxhighlight>

== فشرده سازی ترای ==

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

== نگارخانه ==
<gallery>
File:BitwiseTreesScaling.png|<!--'''Behavior of Fredkin-style tries as a function of size'''{{سخ}}(in this case, nedtries, which is an '''in-place''' implementation, and therefore has a much steeper curve than a dynamic memory based trie implementation){{سخ}}{{سخ}}-->
File:RedBlackTreesScaling.png|<!--'''Behavior of red-black trees as a function of size'''{{سخ}}(in this case, the BSD rbtree.h, which shows classic O(log N) behaviour){{سخ}}{{سخ}}-->
File:HashTableScaling.png|<!--'''Behavior of hash tables as a function of size'''{{سخ}}(in this case, uthash, which when averaged shows classic O(1) behaviour){{سخ}}{{سخ}}-->
</gallery>

== پیوند به بیرون ==

{{چپ‌چین}}
* [http://www.nist.gov/dads/HTML/trie.html NIST's Dictionary of Algorithms and Data Structures: Trie]
* [http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie/ Tries] by Lloyd Allison
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries Using Tries] Topcoder tutorial
* [https://web.archive.org/web/20090319161214/http://linux.thai.net/~thep/datrie/datrie.html An Implementation of Double-Array Trie]
* [http://tom.biodome.org/briandais.html de la Briandais Tree]{{پیوند مرده|date=اکتبر ۲۰۱۹ |bot=InternetArchiveBot }}
* [https://web.archive.org/web/20090428013832/http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/01e485291d150938/9aacb626fa26c516 Discussing a trie implementation in Lisp]
* [https://web.archive.org/web/20120222090138/http://serverkit.org/apiref-wip/node59.html ServerKit "parse trees" implement a form of Trie in C]
{{پایان چپ‌چین}}

== منابع ==
{{پانویس}}
* کتاب CLRS
* ویکی‌پدیای انگلیسی

[[رده:ساختار درختی]]
[[رده:ماشین متناهی]]