درخت سه‌تایی

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

درج

گره‌ها را می‌توان در درخت‌های سه‌تایی در بین سه گره دیگر درج یا بعد از یک گره خارجی اضافه کرد. در درخت‌های سه‌تایی، گره درج شده به عنوان فرزند چپ، وسط یا راست مشخص می‌شود.

گره‌های خارجی

فرض کنید A یک گره خارجی است که قرار است گره‌ای به آن اضافه شود. برای اضافه کردن یک گره به A، گره A گره جدید را به عنوان یکی از فرزندان خود و گره جدید، گره A را به عنوان پدر خود مشخص می‌کند.

گره‌های داخلی

درج به گره‌های داخلی پیچیده‌تر از درج به گره‌های خارجی است. فرض کنید A یک گره داخلی و گره B فرزند گره A باشد. (اگر مطلوب درج فرزند راست است، آنگاه B فرزند راست A است. برای درج فرزند چپ یا وسط هم حالت مشابهی برقرار است.) A فرزندش را گره جدید قرار داده و گره جدید پدرش را A قرار می‌دهد. سپس گره جدید فرزندش را B قرار داده و B پدرش را گره جدید قرار می‌دهد.

حذف

حذف فرآیندی است که در آن یک گره از درخت حذف می‌شود. تنها برخی گره‌های خاص را در یک درخت سه‌تایی می‌توان بدون نیاز به ترمیم ساختمان درخت حذف کرد.

گره با صفر یا یک فرزند

فرض کنید گره A قرار است حذف شود. اگر گره هیچ فرزندی نداشته باشد (گره خارجی)، حذف با تهی کردن اشاره‌گر فرزندِ پدر A صورت می‌گیرد. اگر A یک فرزند داشته باشد، حذف با متصل کردن پدرِ فرزند A به پدر A و متصل کردن فرزندِ پدر A به فرزند A انجام می‌شود.

مقایسه با سایر درخت‌ها

تصویر زیر یک درخت دودویی جست‌وجو است که ۱۲ واژه دو حرفی را نشان می‌دهد. تمام گره‌هایی که فرزند چپ هستند مقادیر کوچک‌تری دارند، در حالی که تمام گره‌هایی که فرزند راست هستند مقادیر بزرگ‌تری دارند. جست‌وجو از ریشه شروع می‌شود. برای یافتن واژه «ON»، آن را با «IN» مقایسه کرده و به سمت شاخه‌ی راست می‌رویم. هر مقایسه می‌تواند به هر حرف از دو کلمه دسترسی داشته باشد.

        in
      /    \
     be    of
    /  \  /  \
   as  by is  or
    \   \  \  / \
    at  he it on to 
درخت جست‌وجوی دیجیتال رشته‌ها را به صورت حرف به حرف ذخیره می‌کند. تصویر بعدی یک درخت است که همان مجموعه‌ ۱۲ کلمه‌ای را نشان می‌دهد:

         _ _ _ _ _ _ _ _ _ _ _ _ _ 
        /     /    / \       \     \
       /     /    /   \       \     \
      a     b    h     i       o     t
     / \   / \   |   / | \    /|\    |
    s  t  e   y  e  n  s  t  f n r   o
   as at be  by he in is it of on or to
هر واژه‌ی ورودی در زیرِ گره‌ای که نشان‌دهندهٔ آن واژه است نشان داده شده است. در یک درخت که واژه‌های آن تنها از حروف کوچک تشکیل شده‌اند، هر گره می‌تواند حداکثر 26 انشعاب داشته باشد. با این روش جست‌وجوها بسیار سریع انجام می‌شوند: جست‌وجو برای «IS» از ریشه شروع می‌شود، به شاخه «I» و سپس به شاخه«S» می‌رود و در گره مطلوب پایان می‌یابد. در هر گره، یک عضو آرایه (یکی از ۲۶ انشعاب) در دسترس قرار می‌گیرد، تهی بودن یا نبودن آن بررسی می‌شود و در صورت تهی نبودن به شاخه بعدی می‌رود.

                    i
              /     |    \
             /      |     \
            b       s      o
         / |  \    / \    |  \
        a  e   h  n   t   n   t
        |   \  |         / \  |
        s    y e        f  r  o
         \
          t
تصویر بالا یک درخت جست‌وجوی سه‌تایی متوازن برای همان مجموعه 12 واژه‌ای است. اشاره‌گرهای کمتر و بیشتر با خطوط مورب (\ یا /) نشان داده شده‌اند، در حالی که اشاره‌گرهای هم‌سطح با خطوط عمودی (|) نمایش داده شده‌اند. جست وجو برای واژه «IS» از ریشه شروع می‌شود، به سمت فرزندِ هم‌سطح با گره، که مقدار «S» را دارد پیش رفته و آنجا پس از دو مقایسه متوقف می‌شود. جست‌وجو برای «AX» سه مقایسه با حرف اول («A») و دو مقایسه با حرف دوم («X») انجام می‌دهد، پیش از آنکه اعلام کند چنین واژه‌ای در درخت وجود ندارد.