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