Trie¶

جست و جو (Search)¶

شما می توانید در \(O(n)\) چک کنید که یک کلمه به طول n در درخت ترای وجود دارد یا نه.

به این صورت که از ریشه شروع می کنید و حرف به حرف جلو می رید و اگر در راسی مانند u هستید و حرف بعدی در کلمه X است اگر راس u با یال X به بچه v می رفت به راس v و حرف بعدی در کلمه می رویم، اگر راس u یال X نداشت به این معناست که کلمه در درخت وجود ندارد. این عملکرد را تا جایی ادامه می دهیم تا کلمه تمام شود(حرف بعدی وجود نداشته باشد). فرض کنید کلمه روی راس w تموم شده است، اگر راس w علامت داشت (و یا مقدار عددی آن طبیعی بود) به این معناست که کلمه وجود دارد و در غیر این صورت کلمه وجود ندارد.

اضافه کردن (Insertion)¶

شما می توانید در \(O(n)\) یک کلمه به طول n را در درخت ترای اضافه کنید.

به این صورت که از ریشه شروع می کنید و حرف به حرف جلو می رید و اگر در راسی مانند u هستید و حرف بعدی در کلمه X است اگر راس u با یال X به بچه v می رفت به راس v و حرف بعدی در کلمه می رویم، اگر کلمه تمام شده راسی که روی آن هستیم را علامت می زنیم(یا به عدد آن یک واحد اضافه می کنیم) و اگر یال X وجود ندارد راس جدیدی می سازیم و راس فعلی را با یال X به آن وصل می کنیم و به حرف بعدی و راس بعدی(راس تازه ساخته شده) می رویم. این روند را ادامه می دهیم تا جایی که یا کلمه تموم شود.

کاربردها¶

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