موضوع مقاله: شماره گذاری درخت فرکتال | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # شماره گذاری درخت فرکتال | مقدمه: در علوم کامپیوتر، درخت فرکتال یکی از انواع داده ساختارهای درخت است که می‌تواند اطلاعات را ذخیره و نگه‌داری کند و می‌توان به اطلاعات آن دسترسی داشت یا همچنین اطلاعات مشخصی را در آن جستجو کرد. | ## بخش 1: شماره گذاری درخت فرکتال | در درخت جستجوی دودویی هر عضو دارای حداکثر دو بچه است (اصطلاحاً فرزند چپ و راست) ولی در درخت فرکتال هر عضو می‌تواند تعداد دلخواهی فرزند داشته باشد و معمولاً یک عدد به عنوان حداکثر تعداد فرزندان وجود دارد که هنگام ساختن فرکتال داده می‌شود. در این داده ساختار در هر عضو تعدادی کلید وجود دارد که در هنگام جستجو به کار می‌آید. همچنین در هر عضو از درخت فرکتال، حافظه‌ای وجود دارد که می‌تواند اطلاعات رو ذخیره کند. درخت فرکتال کاربرد زیادی در دستگاه‌های ورودی خروجی دارد و در ادامه خواهیم دید که که این ساختار برای حافظه‌های خارجی بسیار مناسب است. کلیدها مسئولیت جداسازی اطلاعات را هنگام اضافه‌شدن آن‌ها به فرکتال دارند که در نتیجه تعداد کلیدها یکی کمتر از تعداد فرزندان است. در این صورت این عضو دارای حداکثر n+1 فرزند است که چپ‌ترین فرزند آن مقدار کمتر مساوی با و فرزند دوم آن مقدار کمتر مساوی با و بیشتر از دارد و به همین ترتیب فرزند i-ام مقداری بزگتر از و کمتر مساوی با دارد. در بالا بیان شد که هر عضو دارای یک حافظه است و می‌تواند اطلاعت را در ان ذخیره کند. اگر حافظه نهان آن عضو دارای ظرفیت خالی بود آن مقدار (شی) را به آن اضافه می‌کنیم. | ## بخش 2: شماره گذاری درخت فرکتال | در غیر این صورت زیر درختی که این مقدار باید در آن اضافه شود را پیدا می‌کنیم و تابع درج را به صورت بازگشتی برای آن مقدار (شی) فراخوانی می‌کنیم. در حالتی که ریز درختی که باید مقدار به آن اضافه شود تهی بود، یک برگ جدید ساخته و آن را فرزند عضو فعلی قرار داده و تابع را برای عضو جدید ساخته شده دوباره فراخوانی می‌کنیم. فرض کنید N عضو در درخت ذخیره کرده‌ایم در این صورت چون هر عضو دارای حافظه به اندازه مقدار است و همچنین درخت متوازن است در نتیجه ارتفاع فرکتال است. توجه کنید log باید در مبنای گرفته شود زیرا هر راس فرزند دارد و در نتیجه ارتفاع درخت ا. توجه کنید زمان درج در یک درخت که هر عضو B فرزند دارد برابر با است و در نتیجه هزینه درج در فرکتال کمتر از هزینه درج در درخت است (زمان درج در فرکتال تقریباً نصف زمان درج در درخت است). در هر مرحله باید لیست مقادیر راسی که در آن هستیم را چک کنیم که این است و اگر عنصر یافت شد که کار تمام شده و در غیر اینصورت دنبال زیر درخت مناسب می‌رویم. پیدا کردن زیر درخت مناسب از مرتبه است و چون عمق درخت است در نتیجه مدت زمان جستجو برابر است با است. اما مدت زمان جسجو در درخت است که از اول واضح بود هزینه جستجو در درخت باید کمتر از فرکتال باشد زیرا در فرکتال اعضا دارای حافظه نهان بودند که هزینه جستجو در آن زیاد است. | ## بخش 3: شماره گذاری درخت فرکتال | مقایسه فرکتال با درخت در بالا هزینه‌های زمانی فرکتال و درخت رو با هم مقایسه کردیم. اما در فرکتال هر عضو دارای فرزند و مقدار است و در نتیجه مرتبه حافظه مورد نیاز هر راس است. از طرفی اگر N مقدار را در درخت و فرکتال ذخیره کنیم، درخت دارای N راس و فرکتال دارای راس است. یکی دیگر از مزیت‌های فرکتال زمانی است که از این الگوریتم در حافظه دیسک‌ها استفاده شود. فرض کنید اطلاعات را در دو دیسک ذخیره کرده‌اید که یکی با الگوریتم درخت و دیگری با فرکتال کار می‌کند. در این صورت می‌دانیم هزینه دسترسی و خواندن اطلاعات از دیسک بسیار زیاد است و می‌خواهیم تا جای ممکن دسترسی به دیسک را کاهش دهیم. در این صورت در دیسکی که با الگوریتم درخت کار می‌کند برای خواندن یک مقدار باید ابتدا ان را جستجو کرد و سپس آن را از دیسک خواند و به حافظه نهان آورد. | ## جمع‌بندی | اما اگر دیسک با الگوریتم فرکتال کار کند بعد از پیدا کردن مقدار می‌توان کل حافظه نهان راس را به حافظه نهان آورد و طبق اصل محلی دسترسی‌ها، تعداد دسترسی‌ها به حافظه کمتر می‌شود و مخصوصاً زمانی که بخواهیم عمل نوشتن در حافظه انجام دهیم این اختلاف محسوس تر است.