Trie
============
ترای یک درخت ریشه دار است که برای نگه داشتن چند کلمه استفاده می شود.
هر کلمه به صورت زنجیره ای از حروف است که از ریشه شروع می شود.
اگر دو کلمه پیشوند یکسانی داشته باشند، یک زنجیر یکسان هم در درخت دارند.
فرض کنید تعداد حروف مورد استفاده در کلمات X باشد.
در این صورت هر راس حداکثر X بچه دارد.
دقت کنید که در راس ها حروف وجود ندارند بلکه یال بین هر دو راس دارای حرف است برای فهم بهتر به شکل زیر نگاه کنید.

.. figure:: /_static/dot/Trie.svg
   :width: 50%
   :align: center
   :alt: Trie example

هر راس می تواند یک علامت هم داشته باشد و اگر راسی علامت داشته باشد به این معنی است که در این راس کلمه ای به پایان رسیده است و مسیر ریشه تا این راس آن کلمه است.
اگر ممکن بود چند کلمه یکسان بین کلمات وجود داشته باشد می توان بجای علامت از عدد استفاده کرد و تعداد کلمات پایان یافته در هر راس را نگه داشت.

جست و جو (Search)
------------------
شما می توانید در :math:`O(n)` چک کنید که یک کلمه به طول n در درخت ترای وجود دارد یا نه.

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

اضافه کردن (Insertion)
-----------------
شما می توانید در :math:`O(n)` یک کلمه به طول n را در درخت ترای اضافه کنید.

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

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