در علم رایانه ترای یا درخت پیشوندی یک دادهساختاردرختی است که برای آرایههای شرکتپذیری استفاده میشود که کلیدهای آن معمولاً رشته میباشند. برخلاف یک درخت دودویی جستجو در این درخت هیچ گرهی، کلیدی را که توسط آن گره مشخص میشود ذخیره نمیکند؛ در عوض، موقعیت آن در درخت نشان دهنده کلید مربوط به آن است. تمام فرزندان یک گره پیشوند مشترکی دارند که این پیشوند در گره مربوطه ذخیره میشود. گره ریشه نیز یک رشته خالی است. معمولاً همه گرهها مشخصکننده کلیدها نیستند. فقط برگها و بعضی از گرههای داخلی با کلیدها مرتبط میشوند. گرههای حاوی کلید به نحوی علامتگذاری میشوند تا تمام کلیدها مشخص شوند.
البته یک ترای الزاماً شامل رشتههای کاراکتری نمیباشد، بلکه حتی برای جایگشتهای عددی و مواردی از این قبیل هم میتوان از ترای استفاده کرد.
ترای میتواند به عنوان جایگزین جدول درهم نیز استفاده شود.
مزایا:
۱- جستجوی دادهها در ترای سریعتر است و در بدترین حالت از (O(m میباشد. اما در جدول درهم در شرایط بد این کار از (O(n میباشد.
۲- در ترای تصادم وجود ندارد.
۳- در ترای نیازی به توابع درهم سازی یا تغییر این توابع نیست.
۴- ترای میتواند ترتیب الفبایی داشته باشد.
معایب:
ترای در مواردی ممکن است کندتر باشد. مخصوصاً در جاهایی که دادهها مستقیماً از دیسک سخت یا سایر حافظههای جانبی در دسترس هستند و سرعت دسترسی تصادفی در آنها به مراتب کمتر از حافظه اصلی است.
استفاده رایج ترای در ذخیرهسازی فرهنگ لغت است. برنامههای فرهنگ لغت از توانایی و سرعت بالای ترای در جستجو، درج و حذف کلیدها بهره میبرند.
مرتب سازی
مرتب سازی واژهنگاری یک مجموعه از کلیدها به وسیلهٔ الگوریتمی که از ترای استفاده میکند به این ترتیب است:
- درج تمام کلیدها در ترای
- خروج تمام کلیدها به وسیلهٔ پیمایش پیش ترتیبی
الگوریتم
یک برنامهٔ ساده و با رویکرد استفاده از توابع بازگشتی به زبان سی++ برای ذخیرهٔ اطلاعات در یک درخت ترای و دسترسی و جستجو در این ساختمان دادهها در زیر آمدهاست:
#include<iostream>#include<string>#define alph 26usingnamespacestd;/* node structure (of course it has 26 children) and add and search functions are for lower case alphabets */structnode{boolvalue;//if it's end of word or notnode*next[alph];//all alphabet for next digitsnode()//initialization, the constructor{this->value=0;for(inti=0;i<alph;i++)next[i]=NULL;//there is no next digit initialy}};voidadd(node*head,stringword);boolsearch(node*head,stringquery);intmain(){node*root=newnode();intn;cout<<" enter number of words you wanna insert "<<endl;cin>>n;for(inti=0;i<n;i++){cout<<"enter word "<<endl;stringword;cin>>word;add(root,word);}cout<<" enter number of words you wanna search "<<endl;cin>>n;for(inti=0;i<n;i++){cout<<"enter query "<<endl;stringword;cin>>word;if(search(root,word))cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return0;}voidadd(node*head,stringword){if(word.length()==1){if(head->next[word[0]-'a']==NULL)head->next[word[0]-'a']=newnode();//%22word-%27a%27%22 makes an index alphabet number, 26 more or less of coursehead->next[word[0]-'a']->value=1;return;}else//if(word.length()>1){if(head->next[word[0]-'a']==NULL)head->next[word[0]-'a']=newnode();returnadd(head->next[word[0]-'a'],word.substr(1,word.length()-1));}}boolsearch(node*head,stringquery){if(query.length()==1){if(head->next[query[0]-'a']==NULL)returnfalse;elseif(head->next[query[0]-'a']->value)returntrue;elsereturnfalse;}else{if(head->next[query[0]-'a']==NULL)returnfalse;elsereturnsearch(head->next[query[0]-'a'],query.substr(1,query.length()-1));}}
فشرده سازی ترای
در حالتی که ترای پایستار باشد و نیازی به حذف و درج بعدی در آن نباشد، میتوان با ادغام گرهها، ترای را فشرده کرد.