در علوم کامپیوتر، درخت فرکتال یکی از انواع داده ساختارهای درخت است که می تواند اطلاعات را ذخیره و نگهداری کند و می توان به اطلاعات آن دسترسی داشت یا همچنین اطلاعات مشخصی را در آن جستجو کرد. این داده ساختار شباهت زیادی به درخت دارد. این داده ساختار نیز شبیه درخت تعمیمی از درخت جست جوی دودویی است. در درخت جستجوی دودویی هر عضو دارای حداکثر دو بچه است (اصطلاحاً فرزند چپ و راست) ولی در درخت فرکتال هر عضو می تواند تعداد دلخواهی فرزند داشته باشد و معمولاً یک عدد به عنوان حداکثر تعداد فرزندان وجود دارد که هنگام ساختن فرکتال داده می شود. در این داده ساختار در هر عضو تعدادی کلید وجود دارد که در هنگام جستجو به کار می آید. همچنین در هر عضو از درخت فرکتال، حافظه ای وجود دارد که می تواند اطلاعات رو ذخیره کند. این حافظه بسیار شبیه به حافظه نهان است. درخت فرکتال کاربرد زیادی در دستگاه های ورودی خروجی دارد و در ادامه خواهیم دید که که این ساختار برای حافظه های خارجی بسیار مناسب است.
همان طور که بیان شد هر عضو دارای یک لیست از کلیدها است. کلیدها مسئولیت جداسازی اطلاعات را هنگام اضافه شدن آن ها به فرکتال دارند که در نتیجه تعداد کلیدها یکی کمتر از تعداد فرزندان است. برای مثال فرض کنید یک عضو دارای کلید های a 1 < a 2 < a 3 < . . . < a n {\displaystyle a_{1}<a_{2}<a_{3}<...<a_{n}} باشد. در این صورت این عضو دارای حداکثر n+1 فرزند است که چپ ترین فرزند آن مقدار کمتر مساوی با a 1 {\displaystyle a_{1}} و فرزند دوم آن مقدار کمتر مساوی با a 2 {\displaystyle a_{2}} و بیشتر از a 1 {\displaystyle a_{1}} دارد و به همین ترتیب فرزند i-ام مقداری بزگتر از a i − 1 {\displaystyle a_{i-1}} و کمتر مساوی با a i {\displaystyle a_{i}} دارد. تا این جا شبیه داده ساختار درخت است. در بالا بیان شد که هر عضو دارای یک حافظه است و می تواند اطلاعت را در ان ذخیره کند. حجم این حافظه نهان هنگام هنگام ساختن درخت مشخص می شود.
حال در اینجا با استفاده از زبان برنامه نویسی پایتون یک کلاس برای اعضا می نویسیم.
class Node: def __init__(self, max_child, max_cache, key): self.max_cache = max_cache self.cache = self.max_child = max_child self.child = self.key = key def isfull(self): if len(self.cache) == self.max_cache: return True else: return Falseدرج عضو جدیدویرایشبرای اضافه کردن یک عضو جدید به صورت بازگشتی عمل می کنیم. فرض می کنیم یک مقدار و یک عضو فرکتال به ما داده شده است. اگر حافظه نهان آن عضو دارای ظرفیت خالی بود آن مقدار (شی) را به آن اضافه می کنیم. در غیر این صورت زیر درختی که این مقدار باید در آن اضافه شود را پیدا می کنیم و تابع درج را به صورت بازگشتی برای آن مقدار (شی) فراخوانی می کنیم. در حالتی که ریز درختی که باید مقدار به آن اضافه شود تهی بود، یک برگ جدید ساخته و آن را فرزند عضو فعلی قرار داده و تابع را برای عضو جدید ساخته شده دوباره فراخوانی می کنیم. بقیه توابع مانند جستجو، حذف و … شبیه داده ساختار درخت است با این تفاوت که هر عضو خود دارای یک لیست از مقادیر است به جای یک مقدار.
همان طور که بیان شد هر عضو دارای یک لیست از کلیدها است. کلیدها مسئولیت جداسازی اطلاعات را هنگام اضافه شدن آن ها به فرکتال دارند که در نتیجه تعداد کلیدها یکی کمتر از تعداد فرزندان است. برای مثال فرض کنید یک عضو دارای کلید های a 1 < a 2 < a 3 < . . . < a n {\displaystyle a_{1}<a_{2}<a_{3}<...<a_{n}} باشد. در این صورت این عضو دارای حداکثر n+1 فرزند است که چپ ترین فرزند آن مقدار کمتر مساوی با a 1 {\displaystyle a_{1}} و فرزند دوم آن مقدار کمتر مساوی با a 2 {\displaystyle a_{2}} و بیشتر از a 1 {\displaystyle a_{1}} دارد و به همین ترتیب فرزند i-ام مقداری بزگتر از a i − 1 {\displaystyle a_{i-1}} و کمتر مساوی با a i {\displaystyle a_{i}} دارد. تا این جا شبیه داده ساختار درخت است. در بالا بیان شد که هر عضو دارای یک حافظه است و می تواند اطلاعت را در ان ذخیره کند. حجم این حافظه نهان هنگام هنگام ساختن درخت مشخص می شود.
حال در اینجا با استفاده از زبان برنامه نویسی پایتون یک کلاس برای اعضا می نویسیم.
class Node: def __init__(self, max_child, max_cache, key): self.max_cache = max_cache self.cache = self.max_child = max_child self.child = self.key = key def isfull(self): if len(self.cache) == self.max_cache: return True else: return Falseدرج عضو جدیدویرایشبرای اضافه کردن یک عضو جدید به صورت بازگشتی عمل می کنیم. فرض می کنیم یک مقدار و یک عضو فرکتال به ما داده شده است. اگر حافظه نهان آن عضو دارای ظرفیت خالی بود آن مقدار (شی) را به آن اضافه می کنیم. در غیر این صورت زیر درختی که این مقدار باید در آن اضافه شود را پیدا می کنیم و تابع درج را به صورت بازگشتی برای آن مقدار (شی) فراخوانی می کنیم. در حالتی که ریز درختی که باید مقدار به آن اضافه شود تهی بود، یک برگ جدید ساخته و آن را فرزند عضو فعلی قرار داده و تابع را برای عضو جدید ساخته شده دوباره فراخوانی می کنیم. بقیه توابع مانند جستجو، حذف و … شبیه داده ساختار درخت است با این تفاوت که هر عضو خود دارای یک لیست از مقادیر است به جای یک مقدار.
wiki: شماره گذاری درخت فرکتال