. متن داده‌شده را خلاصه کن

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