مقدمه

شاید یکی از اولین و سنتی ترین چالش های برنامه نویسی ذخیره و خواندن یک سری اطلاعات بر اساس یک رشته حرفی یا مشخصا نام باشد ، روش های زیادی برای اینکار وجود دارد ساده ترین و شاید بدترین راه حل استفاده از آرایه های موازی است که مرتبه زمانی به شدت بدی را به کامپیوتر تحمیل میکند.

یک راه حل خیلی بهتر و کم دردسر تری نیز مثل استفاده از کلاس های Generic کتابخانه استاندارد C++ مثل std::map و std::unordered_map و یا در جاوا مثل java.util.HashMap  و java.util.TreeMap میباشند که بسیار پر کاربرد هم هستند.

اما درخت پیشوندی یک داده ساختار با پیاده سازی ساده است که کاملا کاربردی بوده و در نرم افزار های فرهنگ لغت از این داده ساختار استفاده میشود.

درخت پیشوندی یا Trie چیست؟

این ساختمان داده به گونه ای هست که شاید بیان تعریف آن برای ایده گرفتن برنامه نویسان برای پیاده سازی اش کافی باشد. احتمالا شما با درخت های دو دویی یا Binary Tree پیش از این آشنایی دارید در این درخت ها یک ریشه داریم و هر Node دارای حداکثر دو فرزند میباشد.

مبنای درخت پیشوندی این است که اگر در هر Node به تعداد دلخواه یا برای مثال به تعداد حروف الفبا یال مقدار دار داشته باشیم میتوان به هر Node از این درخت دقیقا یک رشته نسبت داد.

برای مثال اگر برای رسیدن به یک Node میبایست ابتدا از ریشه به یال C و سپس به یال A و بعد از آن به یال R برویم به Node ای میرسیم که همیشه برای رسیدن به آن باید همین مسیر را طی کنیم ، میتوانیم طی یک قرار داد این Node را کلید رشته CAR در نظر بگیریم تفاوت مشخص این داده ساختار این است که کلید CAR در این Node ذخیره نشده تنها با قرار گرفتن در این موقعیت به آن نسبت داده شده است حالا میتوانیم اشاره گر به داده که که قرار است CAR به آن متصل شود را در این Node ذخیره کنیم.

برای مثال در شکل زیر یک Trie میبینید که سه کلمه CAR و CAT و ARC در آن گنجانده شده است، در این درخت هر Node با یک یال به پیشونداش با یک طول کمتر وصل میشود.
یک نمونه Trie
جزئیات پیاده سازی و چالش ها
پیاده سازی این درخت به صورت یک Node شامل تعدادی اشاره گر به Node های بعدی میباشد، اگر یک آرایه از اشاره گر به طول 128 داشته باشیم میتوانیم تمامی کاراکتر های مجاز ASCII را پوشش دهیم، گاهی ممکن است بخواهیم مجموعه ای از کلمات بدون اضافه کردن پیشوندهایشان داشته باشیم در این صورت میتوانیم یا یک اضافه کردن یک متغیر Flag وضعیت نهایی بودن Node را مشخص کنیم.
برای مثال وقتی computer به مجموعه اضافه میشود بدون این متغیر Flag رشته های compute و comp و ... نیز به مجموعه اضافه شده اند ، با داشتن این متغیر میتوانیم تنها برای Node مربوط به computer مقدار True را اختصاص دهیم ، بعد از آن میتوان به پرس و جو ( Query ) برای وجود داشتن یک کلید در مجموعه ، بدون توجه به اینکه Prefix کلید دیگری است یا نه ، پاسخ داد.
چالش دیگری که مطرح میشود تعداد زیاد اشاره گر هاست که باعث هدر رفت حافظه میشود، اگر برای مثال تنها حروف انگلیسی در Trie مجاز میباشد میتوانیم اندازه لیست پیوندی را از 128 به 26 کاهش دهیم ، یا در حالت کلی از یک لیست پیوندی برای اشاره کردن به Node های فرزند استفاده کنیم.

نمونه سوال و خوراک بیشتر
سوال B فینال مسابقات برنامه نویسی بیان 94 ، 2015
مسئله PHONELIST در SPOJ
GeeksforGeeks Tries Tutorial
TopCoder Tries Tutorial