درخت جستجوی سه تایی در علوم رایانه، نوعی درخت پیشوندی است با این تفاوت که گره ها در حالت مشابه با درخت جستجوی دودویی قرار گرفته اند، اما دارای سه فرزند هستند. مانند تمام درخت های پیشوندی، یک درخت جستجوی سه تایی به عنوان داده ساختار آرایه انجمنی با توانایی جستجوی رشته می تواند استفاده شود. از کاربردهای متداول درخت جستجوی سه تایی می توان غلط یاب و تکمیل خودکار را نام برد.
همانند درخت دودویی که هر گره آن دارای یک مقدار و دو اشاره گر به زیردرختان اش است ( زیر درخت اولی دارای عناصر کوچکتر از مقدار عنصر پدر و زیر درخت دومی دارای عناصر بزرگتر از از مقدار پدر ) هر گره از یک درخت جستجوی سه تایی نیز شامل یک کاراکتر و سه اشاره گر به زیر درخت های اول، دوم و زیردرخت سوم می باشد که با نام های فرزند کوچکتر، فرزند مساوی و فرزند بزرگتر شناخته می شوند. یک گره همچنین می تواند اشاره گری به گره پدرش داشته باشد یا شاخصی که مشخص کند آیا به آخر کلمه رسیدیم یا نه. [ ۱] اشاره گر فرزند کوچکتر به گره ای دارای کاراکتر کوچکتر از پدرش اشاره می کند همچنین اشاره گر فرزند بزرگتر به گره ای دارای کاراکتر بزرگتر از پدرش اشاره می کند اما اشاره گر فرزند مساوی به گره ای دارای کاراکتر بعدی در کلمه اشاره می کند. [ ۲] شکل مقابل درخت جستجوی سه تایی شامل رشته های "as" و "at" و "cup" و "cute" و "he" و "i" و "us" را نشان می دهد:
همان طور که در شکل مشاهده می کنیم هر گره در درخت جستجوی سه تایی نشان دهنده یک کاراکتر از رشته ذخیره شده می باشد. همه رشته ها در زیر درخت وسط یک گره با آن پیشوند شروع می شود.
در رویه جستجو ما یک رشته داریم و هر مرحله از این پروسه گره مرتبط با رشته مفروض را پیدا می کنیم. روند جستجو با بررسی کردن گره ریشه آغاز می شود و مشخص می کند کدام یک از حالات زیر اتفاق می افتد. اگر اولین کاراکتر رشته از کاراکتر گره ریشه کمتر بود یک جستجوی بازگشتی با ریشه فرزند کوچکتر فراخوانی می شود. به طور مشابه اگر اولین کاراکتر رشته از کاراکتر گره ریشه بزرگتر بود یک جستجوی بازگشتی با ریشه فرزند بزرگتر فراخوانی می شود؛ و در نهایت اگر اولین کاراکتر رشته مساوی با کاراکتر گره ریشه بود و رشته کاراکتر بیشتری نداشت گره برگشت داده می شود اما اگر کاراکترهای دیگری در رشته وجود داشت کاراکتر اول را از رشته حذف می کنیم و یک جستجوی بازگشتی با ریشه فرزند مساوی فراخوانی می کنیم. روند جستجو را به صورت غیر بازگشتی نیز می توان نوشت که در آن از یک اشاره گری به گره فعلی و اشاره گر دیگری کخ به کاراکتر فعلی در رشته اشاره می کنند استفاده می کنیم.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفهمانند درخت دودویی که هر گره آن دارای یک مقدار و دو اشاره گر به زیردرختان اش است ( زیر درخت اولی دارای عناصر کوچکتر از مقدار عنصر پدر و زیر درخت دومی دارای عناصر بزرگتر از از مقدار پدر ) هر گره از یک درخت جستجوی سه تایی نیز شامل یک کاراکتر و سه اشاره گر به زیر درخت های اول، دوم و زیردرخت سوم می باشد که با نام های فرزند کوچکتر، فرزند مساوی و فرزند بزرگتر شناخته می شوند. یک گره همچنین می تواند اشاره گری به گره پدرش داشته باشد یا شاخصی که مشخص کند آیا به آخر کلمه رسیدیم یا نه. [ ۱] اشاره گر فرزند کوچکتر به گره ای دارای کاراکتر کوچکتر از پدرش اشاره می کند همچنین اشاره گر فرزند بزرگتر به گره ای دارای کاراکتر بزرگتر از پدرش اشاره می کند اما اشاره گر فرزند مساوی به گره ای دارای کاراکتر بعدی در کلمه اشاره می کند. [ ۲] شکل مقابل درخت جستجوی سه تایی شامل رشته های "as" و "at" و "cup" و "cute" و "he" و "i" و "us" را نشان می دهد:
همان طور که در شکل مشاهده می کنیم هر گره در درخت جستجوی سه تایی نشان دهنده یک کاراکتر از رشته ذخیره شده می باشد. همه رشته ها در زیر درخت وسط یک گره با آن پیشوند شروع می شود.
در رویه جستجو ما یک رشته داریم و هر مرحله از این پروسه گره مرتبط با رشته مفروض را پیدا می کنیم. روند جستجو با بررسی کردن گره ریشه آغاز می شود و مشخص می کند کدام یک از حالات زیر اتفاق می افتد. اگر اولین کاراکتر رشته از کاراکتر گره ریشه کمتر بود یک جستجوی بازگشتی با ریشه فرزند کوچکتر فراخوانی می شود. به طور مشابه اگر اولین کاراکتر رشته از کاراکتر گره ریشه بزرگتر بود یک جستجوی بازگشتی با ریشه فرزند بزرگتر فراخوانی می شود؛ و در نهایت اگر اولین کاراکتر رشته مساوی با کاراکتر گره ریشه بود و رشته کاراکتر بیشتری نداشت گره برگشت داده می شود اما اگر کاراکترهای دیگری در رشته وجود داشت کاراکتر اول را از رشته حذف می کنیم و یک جستجوی بازگشتی با ریشه فرزند مساوی فراخوانی می کنیم. روند جستجو را به صورت غیر بازگشتی نیز می توان نوشت که در آن از یک اشاره گری به گره فعلی و اشاره گر دیگری کخ به کاراکتر فعلی در رشته اشاره می کنند استفاده می کنیم.
wiki: درخت جستجوی سه تایی