درخت هشتتایی (به انگلیسی: Octree) یک دادهساختار درخت است که در آن هر گره داخلی دقیقاً هشت فرزند دارد. درختهای هشتتایی اغلب برای افراز کردن یک فضای سهبعدی از طریق تقسیم بازگشتی آن فضا به هشت قسمت مساوی استفاده میشوند. درختهای هشتتایی در واقع معادل چاردرخت در حالت سه بعدی اند. اسم این درخت از دو کلمه انگلیسی oct و tree تشکیل شدهاست، اما توجه کنید که این کلمه معمولاً به صورت octree فقط با یک حرف t نوشته میشود. درختهای هشتتایی غالباً در گرافیک سهبعدی رایانهای و موتورهای بازی سهبعدی استفاده میشوند.
هر گره در یک درخت هشتتایی فضا را به هشت اکتان تقسیم میکند. در یک درخت هشتتایی نقطهای ناحیهای، هر گره در واقع یک نقطه سهبعدی را نگه میدارد که مرکز قسمتی است که مربوط به آن گره است؛ این نقطه گوشه مشترک هر هشت فرزند گره است. در یک درخت هشتتایی نقطهای که حول آن فضا تقسیم میشود بهطور ضمنی مرکز قسمتی است که گره نمایش میدهد. گره ریشه از یک درخت هشتتایی PR میتواند فضای نامحدود را نشان دهد؛ در حالی که گره ریشه از یک درخت هشتتایی MX باید یک فضای محدود را نشان دهد که مرکزهای هر قسمت قابل تعریف باشند. توجه داشته باشید که درخت هشتتایی با درخت کیدی متفاوت است. درختهای کیدی در راستای یک بعد تقسیمبندی انجام میدهند اما درختهای هشتتایی پیرامون یک نقطه (در راستای سهبعد) تقسیمبندی انجام میدهند. همچنین درختهای کیدی همواره دودوییاند که در مورد درختهای هشتتایی این گونه نیست. با بهکارگیری جستجوی عمق اول (dfs) باید گرهها پیمایش شوند اما فقط سطوح مورد نیاز در نظر گرفته شوند.
درخت هشتتایی برای گرافیک سهبعدی رایانهای اولین بار توسط دونالر میقر در مؤسسه پلیتکنیک رنسلیر استفاده شد، که در گزارش سال ۱۹۸۰ با عنوان "رمزگذاری درختهای هشتتایی: یک راه جدید برای نمایش دوباره، دستکاری و نمایش دلخواه اشیاء سهبعدی به وسیلهٔ کامپیوتر"[۱] آن را شرح داد. او صاحب ثبت اختراع ۱۹۹۵ (با تاریخ اولویت ۱۹۸۴) با عنوان "تولید سریع عکس از اشیاء جامد پیچیده به وسیلهٔ رمزگذاری درخت هشتتایی"[۲] نیز بود.
الگوریتم درجهبندی رنگ در درخت هشتتایی توسط گرواتز و پورگاتوفر در سال ۱۹۸۸ ابداع شد. این الگوریتم دادههای مربوط به رنگ یک تصویر را به صورت درخت هشتتایی درآورده و درخت را تا عمق ۹ سطح کدگذاری میکند. از آنجا که در سیستم رنگی آرجیبی سه مؤلفه رنگی وجود دارد و ۸=۳^۲ از درخت هشتتایی استفاده میشود. شماره مربوط به یک گره در سطح بالا با یک فرمول مشخص میشود که از پرارزشترین بیتهای مؤلفههای رنگی قرمز، سبز و آبی استفاده میکند، مثلاً 4r + 2g + b. سطح بعدی یا پایینتر از بیتهای پرارزش بعدی استفاده میکند و به همین ترتیب جلو میرود. گاهی بیتهای کم ارزش نادیده گرفته میشوند تا اندازه درخت کاهش یابد. این الگوریتم از لحاظ مصرف حافظه بسیار بهینه است چرا که اندازه درخت میتواند محدود باشد. سطح پایین یک درخت هشتتایی از برگهایی که به دادههای رنگی مربوطند و در درخت نمایش داده نمیشوند، تشکیل میگردد. این گرهها در ابتدا حاوی تکبیتها هستند. اگر تعداد بیشتری از یک مقدار دلخواه رنگ از پالتها وارد درخت شوند، اندازه درخت میتواند به صورت پیوسته کاهش یابد. این کار با دنبال کردن یک گره سطح پایین و افزایش میانگین مقدار بیتی آن تا رسیدن به برگ ادامه مییابد. در واقع به این ترتیب قسمتی از درخت هرس میشود. هنگامی که این کار بهطور کامل انجام شود، با پیمایش همهٔ مسیرهای درخت تا برگها و در نظر گرفتن بیتها در طول مسیر میتوان بهطور تقریبی تعداد رنگهای لازم را به دست آورد.
مشارکتکنندگان ویکیپدیا. «Octree». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۳۰ اردیبهشت ۱۳۹۳.