در علوم رایانه، درخت سه تایی یک ساختمان داده از نوع درخت است که در آن هر گره حداکثر سه گره فرزند دارد که معمولاً با عناوین «چپ»، «وسط» و «راست» شناخته می شوند. گره های دارای فرزند، گره های پدر هستند و گره های فرزند می توانند شامل اشاره گرهایی به پدرانشان باشند. خارج از درخت ریشه دار، اغلب اشاره گری به گره ریشه ( جد همهٔ گره ها ) وجود دارد. با شروع از گره ریشه و دنبال کردن مراجع به صورت مکرر به فرزند چپ، وسط یا راست، می توان به هر گره دل خواهی در ساختمان داده دسترسی داشت.
درخت های سه تایی برای پیاده سازی درخت سه تایی جست وجو و هرم سه تایی استفاده می شوند.
• یال جهت دار ـ رابطِ پدر به فرزند
• ریشه ـ گره بدون پدر. در یک درخت ریشه دار حداکثر یک ریشه وجود دارد.
• گره برگ ـ گره ای است که فرزندی ندارد.
• گره فرزند ـ گره هایی که در زیر یک گره واقع شده اند.
• عمق ـ طول مسیر ریشه تا گره است. مجموعهٔ همه گره هایی که عمق یکسانی دارند، یک سطح از درخت نامیده می شوند. عمق گره ریشه صفر است.
• ارتفاع ـ طول بلندترین مسیر از ریشه تا یک برگ در درخت است. یک درخت ( ریشه دار ) با تنها یک گره ( ریشه ) ارتفاعی برابر با صفر دارد. در شکل مثال، ارتفاع درخت برابر ۲ است.
• برادر ـ گره هایی که پدر یکسانی دارند.
- گره p جد گره q است اگر در مسیر q به ریشه قرار داشته باشد. در این صورت q نواده p نامیده می شود.
- اندازه یک گره برابر تعداد نوادگان آن گره به اضافهٔ یک است. ( با احتساب خود گره )
• حداکثر تعداد گره ها
- اگر h ارتفاع درخت سه تایی و ( M ( h حداکثر تعداد گره های یک درخت سه تایی با ارتفاع h باشد:
- هر درخت با ارتفاع h حداکثر ∑ i = 0 h 3 i گره دارد.
در پیاده سازی ضمنی ( با استفاده از آرایه ) درخت:
• اگر گره N {\displaystyle N} ، در خانهٔ [TREE[k باشد، فرزند چپ آن در [TREE[3k - 1 ذخیره می شود.
• فرزند وسط در [TREE[3k ذخیره می شود.
• فرزند راست در [TREE[3k+1 ذخیره می شود.
گره ها را می توان در درخت های سه تایی در بین سه گره دیگر درج یا بعد از یک گره خارجی اضافه کرد. در درخت های سه تایی، گره درج شده به عنوان فرزند چپ، وسط یا راست مشخص می شود.
فرض کنید A یک گره خارجی است که قرار است گره ای به آن اضافه شود. برای اضافه کردن یک گره به A، گره A گره جدید را به عنوان یکی از فرزندان خود و گره جدید، گره A را به عنوان پدر خود مشخص می کند.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفدرخت های سه تایی برای پیاده سازی درخت سه تایی جست وجو و هرم سه تایی استفاده می شوند.
• یال جهت دار ـ رابطِ پدر به فرزند
• ریشه ـ گره بدون پدر. در یک درخت ریشه دار حداکثر یک ریشه وجود دارد.
• گره برگ ـ گره ای است که فرزندی ندارد.
• گره فرزند ـ گره هایی که در زیر یک گره واقع شده اند.
• عمق ـ طول مسیر ریشه تا گره است. مجموعهٔ همه گره هایی که عمق یکسانی دارند، یک سطح از درخت نامیده می شوند. عمق گره ریشه صفر است.
• ارتفاع ـ طول بلندترین مسیر از ریشه تا یک برگ در درخت است. یک درخت ( ریشه دار ) با تنها یک گره ( ریشه ) ارتفاعی برابر با صفر دارد. در شکل مثال، ارتفاع درخت برابر ۲ است.
• برادر ـ گره هایی که پدر یکسانی دارند.
- گره p جد گره q است اگر در مسیر q به ریشه قرار داشته باشد. در این صورت q نواده p نامیده می شود.
- اندازه یک گره برابر تعداد نوادگان آن گره به اضافهٔ یک است. ( با احتساب خود گره )
• حداکثر تعداد گره ها
- اگر h ارتفاع درخت سه تایی و ( M ( h حداکثر تعداد گره های یک درخت سه تایی با ارتفاع h باشد:
- هر درخت با ارتفاع h حداکثر ∑ i = 0 h 3 i گره دارد.
در پیاده سازی ضمنی ( با استفاده از آرایه ) درخت:
• اگر گره N {\displaystyle N} ، در خانهٔ [TREE[k باشد، فرزند چپ آن در [TREE[3k - 1 ذخیره می شود.
• فرزند وسط در [TREE[3k ذخیره می شود.
• فرزند راست در [TREE[3k+1 ذخیره می شود.
گره ها را می توان در درخت های سه تایی در بین سه گره دیگر درج یا بعد از یک گره خارجی اضافه کرد. در درخت های سه تایی، گره درج شده به عنوان فرزند چپ، وسط یا راست مشخص می شود.
فرض کنید A یک گره خارجی است که قرار است گره ای به آن اضافه شود. برای اضافه کردن یک گره به A، گره A گره جدید را به عنوان یکی از فرزندان خود و گره جدید، گره A را به عنوان پدر خود مشخص می کند.
wiki: درخت سه تایی