ترای یا درخت پیش‌وندی یک داده‌ساختار درختی است که برای نگاشت‌ها استفاده می‌شود (نگاشت مجموعه‌ای از زوج مرتب‌های (کلید، مقدار) است که هر کلید حداکثر یک‌بار می‌آید). وقتی از ترای استفاده می‌کنیم، کلیدها معمولاً رشته هستند. البته اگر نگاشتی در کار نباشد و صرفاً تعدادی رشته داشته باشیم، باز هم می‌توان برای پردازش آن‌ها از ترای استفاده کرد.

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

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

زمان جستجو، درج و حذف کلیدها در ترای از مرتبه طول کلید است. اما در یک درخت دودویی جست‌وجو با تعداد گره‌ی $n$ باید به طور متوسط $\mathcal{O}(\log n)$ مقایسه انجام داد که تعداد مقایسه‌ها در بدترین حالت به $n$ نزدیک می‌شود.

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

درخت جستجوی دودویی برای هر داده‌ی مقایسه‌پذیری قابل استفاده است. اما ترای برای داده‌های بسیار محدودتری استفاده می‌شود.

Trie.cpp

void insert(string s) {
    node *cur = root;
    for (int i = 0; i < (int) s.size(); i++) {
        if (!cur-> cld(s[i]))
            cur-> cld(s[i]) = new node;
        cur = cur-> cld(s[i]);
    }
    cur-> ex = true;
}
bool search(string s) {
    node *cur = root;
    for (int i = 0; i < (int) s.size(); i++) {
        if (!cur-> cld(s[i]))
            return false;
        cur = cur-> cld(s[i]);
    }
    return cur-> ex;
}

• برای ذخیره‌سازی و دسترسی سریع به رشته‌های یک لغت‌نامه کاربرد فراوانی دارد.
• برای برخی سیستم‌های تکمیل خودکار رشته (autocomplete) استفاده می‌شود.
• می‌تواند در بعضی شرایط به عنوان جای‌گزینی برای جدول‌های درهم‌سازی استفاده بشود.
• از ترای برای مرتب‌سازی داده‌ها در زمان خطی استفاده می‌شود. مثلاً اگر مجموعه‌ای از رشته‌ها را در ترای درج کنیم و نمایش پیش‌ترتیب آن را چاپ کنیم، رشته‌ها به ترتیب لغت‌نامه‌ای مرتب می‌شوند. همچنین اگر ترای را با مجموعه‌ای از اعداد بسازیم، جستجوی سطح اول اعداد را به ترتیب می‌پیماید.