درخت سه‌تایی

یک درخت سه‌تایی ساده با اندازه ۱۰ و ارتفاع ۲.

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

درخت‌های سه‌تایی برای پیاده‌سازی درخت سه‌تایی جست‌وجو و هرم سه‌تایی استفاده می‌شوند.

تعاریف

• یال جهت‌دار ـ رابطِ پدر به فرزند
• ریشه ـ گره بدون پدر. در یک درخت ریشه‌دار حداکثر یک ریشه وجود دارد.
• گره برگ ـ گره‌ای است که فرزندی ندارد.
• گره فرزند ـ گره‌هایی که در زیر یک گره واقع شده‌اند.
• عمق ـ طول مسیر ریشه تا گره است. مجموعهٔ همه گره‌هایی که عمق یکسانی دارند، یک سطح از درخت نامیده می‌شوند. عمق گره ریشه صفر است.
• ارتفاع ـ طول بلندترین مسیر از ریشه تا یک برگ در درخت است. یک درخت (ریشه‌دار) با تنها یک گره (ریشه) ارتفاعی برابر با صفر دارد. در شکل مثال، ارتفاع درخت برابر ۲ است.
• برادر ـ گره‌هایی که پدر یکسانی دارند.

-گره p جد گره q است اگر در مسیر q به ریشه قرار داشته باشد. در این صورت q نواده p نامیده می‌شود.

-اندازه یک گره برابر تعداد نوادگان آن گره به اضافهٔ یک است. (با احتساب خود گره)

خواص درخت‌های سه‌گانه

• حداکثر تعداد گره‌ها

-اگر h ارتفاع درخت سه‌تایی و (M(h حداکثر تعداد گره‌های یک درخت سه‌تایی با ارتفاع h باشد:

M(h)	h
۱	۰
۴	۱
۱۳	۲
۴۰	۳

–$M(h)=1+3+9+\cdots +3^{h}=\sum _{i=0}^{h}3^{i}$

-هر درخت با ارتفاع h حداکثر $\sum _{i=0}^{h}3^{i}$ گره دارد.

در پیاده‌سازی ضمنی (با استفاده از آرایه) درخت:

• اگر گره $N$، در خانهٔ [TREE[k باشد، فرزند چپ آن در [TREE[3k-1 ذخیره می‌شود.
• فرزند وسط در [TREE[3k ذخیره می‌شود.
• فرزند راست در [TREE[3k+1 ذخیره می‌شود.

عملیات متداول

درج

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

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

فرض کنید 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») انجام می‌دهد، پیش از آنکه اعلام کند چنین واژه‌ای در درخت وجود ندارد.

مثال‌هایی از درخت‌های سه‌تایی

• درخت سه‌تایی جستجو
• هرم سه‌تایی
• یک درخت سه‌تایی بی‌نهایت شامل تمامی سه‌گانه‌های اصلی فیثاغورس، در درخت سه‌گانه‌های اصلی فیثاغورس و در فرمول‌هایی برای تولید سه‌گانه‌های فیثاغورس شرح داده شده است و گره ریشهٔ آن سه‌گانهٔ [۳، ۴، ۵] است.

جستارهای وابسته

• درخت دودویی
• ساختار درختی

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Ternary tree». در دانشنامهٔ ویکی‌پدیای انگلیسی.