فهرست مندرجات

عنوان مطلب

تعریف

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

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

مقایسه با درخت‌های جست‌وجوی دودویی

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

زمان جستجو، درج و حذف کلیدها در ترای از مرتبه طول کلید است. اما در یک درخت دودویی جست‌وجو با تعداد گره‌ی $n$ باید به طور متوسط $O(lg 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;
}

کاربردها