درخت (ساختار داده) کیست؟ توضیح بده.
"درخت در علوم کامپیوتر، ساختار دادهٔ پر استفاده است که شبیه به یک ساختار درختی با مجموعه‌ای از گره‌های متصل به هم است. درخت یک گراف همبند بدون دور است. اکثر نویسندگان این قید را نیز اضافه می‌کنند که گراف باید بدون جهت باشد. به علاوه بعضی قید بدون وزن بودن یال‌ها را نیز اضافه می‌کنند.""گره‌ها"."گره‌های ریشه"."بالاترین گره درخت گره ریشه نام دارد. پس گره ریشه پدر ندارد. این گره، گرهی است که عملیات روی درخت معمولاً از آن شروع می‌شود.( هر چند بعضی الگوریتم‌ها از برگ شروع شده و به ریشه ختم می‌شوند ). بقیهٔ گره‌ها با دنبال کردن یال‌ها از گره ریشه قابل دسترسی اند. در نمودار درخت عموماً گره ریشه در بالا رسم می‌شود. در بعضی درخت ها، مثل پشته ها، گره ریشه ویژگی‌های خاصی دارند. هر گره در یک درخت را می‌توان ریشهٔ یک زیر درخت در نظر گرفت. که این زیر درخت درختی است ریشه دار که آن گره ریشهٔ آن است.""گره‌های برگ"."پایین‌ترین گره‌های یک درخت گره‌های برگ نام دارند. چون این گره‌ها زیرترین گره هستند هیچ فرزندی ندارند.""گره‌های داخلی"."یک گره داخلی هر گرهی است که فرزند داشته باشد پس برگها گره داخلی نیستند.""زیر درخت ها"."زیر درخت بخشی از درخت است که خود یک درخت کامل را تشکیل می‌دهد. هر گره در درخت T با تمام گره‌های زیر آن زیر درخت درخت T را تشکیل می‌دهد. زیر درخت متناظر با گره ریشه درخت اصلی است. زیر درخت متناظر با بقیهٔ رئوس زیر درخت سره گفته می‌شود.""مرتبهٔ درخت"."درخت‌ها دو نوع اصلی هستند. درخت بازگشتی یا درخت نامرتب درختی است که فرزندان هر رأس ترتیب خاصی ندارند و درخت مرتب درختی است که در آن ترتیب خاصی اعمال می‌شود. برای مثال می‌توان به هر رأس عددی طبیعی مربوط کرد.""محتویات اعضا"."هر عضو در درخت دارای یک لیست از کلیدها است. کلیدها مسئولیت جداسازی اطلاعات را هنگام اضافه‌شدن آن‌ها به درخت دارند که در نتیجه تعداد کلیدها یکی کمتر از تعداد فرزندان است. برای مثال فرض کنید یک عضو دارای کلید هایformula_1 باشد. در این صورت این عضو دارای حداکثر n+1 فرزند است که چپ‌ترین فرزند آن مقدار کمتر مساوی با formula_2 و فرزند دوم آن مقدار کمتر مساوی با formula_3 و بیشتر از formula_2 دارد و به همین ترتیب فرزند i-ام مقداری بزرگتر از formula_5 و کمتر مساوی با formula_6 دارد.""حال در اینجا با استفاده از زبان برنامه‌نویسی پایتون یک کلاس برای اعضا می‌نویسیم."class Node: def __init__(self, max_cache, key): 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"درج عناصر"."اضافه کردن یک عضو جدید شبیه به درخت دودویی است.فرض کنید می خواهید مقدار c را به درخت اضافه کنید.ابتدا ریشه را در نظر می‌گیریم.بعد با مقایسه کردن مقدار c با کلیدها زیر درختی که این مقدار باید به ان اضافه شود را پیدا می‌کنیم.این روند را ادامه می‌دهیم تا به یک راس ایجاد نشده برسیم سپس با اضافه‌کردن ان مقدار c را به درخت اضافه میکنیم.""حذف عناصر"."حذف یک عنصر هم دقیقاً شبیه درخت دودویی است.ابتدا باید راسی را که می خواهیم حذف کنیم پیدا کنیم که این کار همانند زمانی است که می خواستیم هنگام درج راس خالی مناسب را پیدا کنیم.بعد از پیدا کردن راس مناسب کافی است مانند درخت دودویی ، بزرگ‌ترین راس در زیردرخت ان را در ان جایگزین کنیم و ان راس را حذف کنیم.اگر فرض کنیم درخت متوازن است در نتیجه هزینه درج و حذف هم برابر است با پیدا کردن راس مناسب که برابر با ارتفاع درخت که formula_7 است می‌باشد .""مقایسه فرکتال با درخت"."در بالا هزینه‌های زمانی فرکتال و درخت رو با هم مقایسه کردیم. اما این دو از نظر مقدار حافظه بسیار متفاوت هستند. در درخت هر عضو B بچه دارد و در نتیجه هر راس حافظه‌ای از مرتبه B دارد. اما در فرکتال هر عضو دارای formula_8 فرزند و formula_8 مقدار است و در نتیجه مرتبه حافظه مورد نیاز هر راس formula_8 است. از طرفی اگر N مقدار را در درخت و فرکتال ذخیره کنیم، درخت دارای N راس و فرکتال دارای formula_11 راس است. در نتیجه حافظه مورد نیاز درخت B برابر فرکتال است.""یکی دیگر از مزیت‌های فرکتال زمانی است که از این الگوریتم در حافظه دیسک‌ها استفاده شود. فرض کنید اطلاعات را در دو دیسک ذخیره کرده‌اید که یکی با الگوریتم درخت و دیگری با فرکتال کار می‌کند. در این صورت می‌دانیم هزینه دسترسی و خواندن اطلاعات از دیسک بسیار زیاد است و می‌خواهیم تا جای ممکن دسترسی به دیسک را کاهش دهیم. در این صورت در دیسکی که با الگوریتم درخت کار می‌کند برای خواندن یک مقدار باید ابتدا ان را جستجو کرد و سپس آن را از دیسک خواند و به حافظه نهان آورد. حال برای مقدار بعدی دوباره باید همین کار را انجام داد. اما اگر دیسک با الگوریتم فرکتال کار کند بعد از پیدا کردن مقدار می‌توان کل حافظه نهان راس را به حافظه نهان آورد و طبق اصل محلی دسترسی‌ها، تعداد دسترسی‌ها به حافظه کمتر می‌شود و مخصوصاً زمانی که بخواهیم عمل نوشتن در حافظه انجام دهیم این اختلاف محسوس تر است."