موضوع مقاله: درخت جستجوی سه‌تایی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت جستجوی سه‌تایی | مقدمه: درخت جستجوی سه تایی در علوم رایانه، نوعی درخت پیشوندی است با این تفاوت که گره‌ها در حالت مشابه با درخت جستجوی دودویی قرار گرفته‌اند، اما دارای سه فرزند هستند. | ## بخش 1: درخت جستجوی سه‌تایی | مانند تمام درخت‌های پیشوندی، یک درخت جستجوی سه تایی به عنوان داده ساختار آرایه انجمنی با توانایی جستجوی رشته می‌تواند استفاده شود. از کاربردهای متداول درخت جستجوی سه تایی می‌توان غلط یاب و تکمیل خودکار را نام برد. یک گره همچنین می‌تواند اشاره گری به گره پدرش داشته باشد یا شاخصی که مشخص کند آیا به آخر کلمه رسیدیم یا نه. اشاره گر فرزند کوچکتر به گره‌ای دارای کاراکتر کوچکتر از پدرش اشاره می‌کند همچنین اشاره گر فرزند بزرگتر به گره‌ای دارای کاراکتر بزرگتر از پدرش اشاره می‌کند اما اشاره گر فرزند مساوی به گره‌ای دارای کاراکتر بعدی در کلمه اشاره می‌کند. شکل مقابل درخت جستجوی سه تایی شامل رشته‌های "as" و "at" و "cup" و "cute" و "he" و "i" و "us" را نشان می‌دهد: همان‌طور که در شکل مشاهده می‌کنیم هر گره در درخت جستجوی سه تایی نشان دهنده یک کاراکتر از رشته ذخیره شده می‌باشد. عملیات جستجو در رویه جستجو ما یک رشته داریم و هر مرحله از این پروسه گره مرتبط با رشته مفروض را پیدا می‌کنیم. روند جستجو با بررسی کردن گره ریشه آغاز می‌شود و مشخص می‌کند کدام یک از حالات زیر اتفاق می‌افتد. | ## بخش 2: درخت جستجوی سه‌تایی | اگر اولین کاراکتر رشته از کاراکتر گره ریشه کمتر بود یک جستجوی بازگشتی با ریشه فرزند کوچکتر فراخوانی می‌شود. به طور مشابه اگر اولین کاراکتر رشته از کاراکتر گره ریشه بزرگتر بود یک جستجوی بازگشتی با ریشه فرزند بزرگتر فراخوانی می‌شود؛ و در نهایت اگر اولین کاراکتر رشته مساوی با کاراکتر گره ریشه بود و رشته کاراکتر بیشتری نداشت گره برگشت داده می‌شود اما اگر کاراکترهای دیگری در رشته وجود داشت کاراکتر اول را از رشته حذف می‌کنیم و یک جستجوی بازگشتی با ریشه فرزند مساوی فراخوانی می‌کنیم. روند جستجو را به صورت غیر بازگشتی نیز می‌توان نوشت که در آن از یک اشاره گری به گره فعلی و اشاره گر دیگری کخ به کاراکتر فعلی در رشته اشاره می‌کنند استفاده می‌کنیم. درج رویه درج در درخت جستجوی سه تایی همانند رویه جستجو به صورت بازگشتی تعریف می‌شود بدین صورت که همواره بر روی یکه از گره‌های درخت و کلیدی (رشته‌ای) که به تدریج در حال کوچکتر شدن است فراخوانی می‌شود. اگر این روند به گره‌ای برسد که هنوز ساخته نشده بود آن را می‌سازد و کاراکتر را به آن واگذار می‌کند. چه گره جدید ساخته شده باشد یا نه این روال بررسی می‌کند که مقدار کاراکتر کلید بزرگتر، مساوی یا کوچکتر از مقدار گره می‌باشد و در هرکدام از حالت‌ها یک فراخوانی مناسب انجام می‌دهد. اگر با این حال، کاراکتر اول کلید مساوی با مقدار گره باشد روند درج بر روی فرزند مساوی فراخوانی می‌شود و کاراکتر اول کلید حذف می‌شود. | ## بخش 3: درخت جستجوی سه‌تایی | درخت جستجوی سه تایی مانند درخت دودویی و دیگر ساختمان داده‌ها می‌تواند بر اساس کلیدها منحط ساخته شود. پیچیدگی زمانی پیچیدگی زمانی درخت جستجوی سه تایی به طور قابل ملاحظه‌ای توسط ورودی‌ها تغییر می‌کند. همچنین درخت سه تایی وقتی ورودی‌ها رشته‌های مشابه باشند یا دارای پیشوند یکسانی باشند عملکرد بهتری دارد. متناوباً درخت جستجوی سه تایی هنگام ذخیره‌سازی تعداد زیادی رشته‌های کوچک مرتبط، مفید واقع خواهد شد (مانند لغات در یک فرهنگ لغت). پیچیدگی زمانی درخت جستجوی سه تایی همانند درخت جستجوی دودویی در زمان لگاریتمی انجام می‌شود، اما هنگامی که فاسد (بدترین حالت) باشد اردر زمانی آن خطی است. چند کاربرد متداول یا اغلب مفید این درخت عبارت است از: همیشه از ترای (درخت عبارت) می‌توان استفاده کرد اما داده ساختاری با مصرف حافظه کمتر ارجحیت دارد. | ## جمع‌بندی | یک داده ساختار تند که فضای کمی مصرف می‌کند برای نگاشت رشته‌ها به داده‌های دیگر مورد استفاده قرار می‌گیرد.