درخت پیشوندی
در علم رایانه ترای یا درخت پیشوندی یک دادهساختار درختی است که برای آرایههای شرکتپذیری استفاده میشود که کلیدهای آن معمولاً رشته میباشند. برخلاف یک درخت دودویی جستجو در این درخت هیچ گرهی، کلیدی را که توسط آن گره مشخص میشود ذخیره نمیکند؛ در عوض، موقعیت آن در درخت نشان دهنده کلید مربوط به آن است. تمام فرزندان یک گره پیشوند مشترکی دارند که این پیشوند در گره مربوطه ذخیره میشود. گره ریشه نیز یک رشته خالی است. معمولاً همه گرهها مشخص کننده کلیدها نیستند. فقط برگها و بعضی از گرههای داخلی با کلیدها مرتبط میشوند. گرههای حاوی کلید به نحوی علامتگذاری میشوند تا تمام کلیدها مشخص شوند.
البته یک ترای الزاما شامل رشتههای کاراکتری نمیباشد، بلکه حتی برای جایگشتهای عددی و مواردی از این قبیل هم میتوان از ترای استفاده کرد.
محتویات |
مزایای ترای نسبت به درخت دودویی جستجو[ویرایش]
جستجوی کلیدها در ترای سریعتر است و از مرتبه طول کلید میباشد. اما در یک درخت دودویی جستجو با تعداد گره n باید به طور متوسط (O(nlgn مقایسه انجام داد که تعداد مقایسهها در بدترین حالت به n نزدیک میشود.
ترای زمانی که شامل تعداد زیادی از رشتههای کوچک باشد، فضای کمتری نسبت به درخت دودویی جستجو برای ذخیره اشغال میکند.
کاربردها[ویرایش]
جایگزینی جدول درهم[ویرایش]
ترای میتواند به عنوان جایگزین جدول درهم نیز استفاده شود.
مزایا:
۱- جستجوی دادهها در ترای سریعتر است و در بدترین حالت از (O(m میباشد. اما در جدول درهم در شرایط بد این کار از (O(n میباشد.
۲- در ترای تصادم وجود ندارد.
۳- در ترای نیازی به توابع درهم سازی و یا تغییر این توابع نیست.
۴- ترای میتواند ترتیب الفبایی داشته باشد.
معایب:
ترای در مواردی مکن است کندتر باشد. مخصوصا در جاهایی که دادهها مستقیما از دیسک سخت یا سایر حافظههای جانبی در دسترس هستند و سرعت دسترسی تصادفی در آنها به مراتب کمتر از حافظه اصلی است.
نمایش فرهنگ لغت[ویرایش]
استفاده رایج ترای در ذخیره سازی فرهنگ لغت است. برنامههای فرهنگ لغت از توانایی و سرعت بالای ترای در جستجو، درج و حذف کلیدها بهره میبرند.
مرتب سازی[ویرایش]
مرتب سازی واژه نگاری یک مجموعه از کلیدها بوسیله الگوریتمی که از ترای استفاده میکند به این ترتیب است:
- درج تمام کلیدها در ترای
- خروج تمام کلیدها بوسیله پیمایش پیش ترتیبی
فشرده سازی ترای[ویرایش]
در حالتی که ترای پایستار باشد و نیازی به حذف و درج بعدی در آن نباشد، میتوان با ادغام گرهها، ترای را فشرده کرد.
|
|||||||||||||||||
نگارخانه[ویرایش]
پیوند به بیرون[ویرایش]
مراجع[ویرایش]
- کتاب CLRS
- ویکیپدیای انگلیسی
