درخت (ساختار داده)
درخت در علوم کامپیوتر، ساختار دادهٔ پر استفاده است که شبیه به یک ساختار درختی با مجموعه‌ای از گره‌های متصل به هم است. درخت یک گراف همبند بدون دور است. اکثر نویسندگان این قید را نیز اضافه می‌کنند که گراف باید بدون جهت باشد. به علاوه بعضی قید بدون وزن بودن یال‌ها را نیز اضافه می‌کنند.
هر گره در درخت تعدادی (صفر یا بیشتر) گره فرزند دارد، که در زیر آن در درخت قرار دارند (به طور قراردادی، درخت به سمت پایین رشد می‌کند، برخلاف آنچه در طبیعت می بینیم). یک گره که فرزند دارد گره پدر آن فرزند گفته می‌شود. یک گره حداکثر ۱ پدر دارد. ارتفاع یک گره طول طولانی‌ترین مسیر پایین رو از آن گره به یک برگ است. طول ریشه طول درخت نامیده می‌شود. مسیری که از گره به ریشه وصل می‌شود مسیر ریشه نام دارد و طول این مسیر عمق آن گره است. بالاترین گره درخت گره ریشه نام دارد. پس گره ریشه پدر ندارد. این گره گرهی است که عملیات روی درخت معمولاً از آن شروع می‌شود.( هر چند بعضی الگوریتم‌ها از برگ شروع شده و به ریشه ختم می‌شوند ). بقیهٔ گره‌ها با دنبال کردن یالها از گره ریشه قابل دسترسی اند درنمودار درخت عموماً گره ریشه در بالا رسم می‌شود. در بعضی درخت ها، مثل پشته ها، گره ریشه ویژگی‌های خاصی دارند. هر گره در یک درخت را می‌توان ریشهٔ یک زیر درخت در نظر گرفت. که این زیر درخت درختی است ریشه دار که آن گره ریشهٔ آن است.
پایین‌ترین گره‌های یک درخت گره‌های برگ نام دارند. چون این گره‌ها زیرترین گره هستند هیچ فرزندی ندارند. یک گره داخلی هر گرهی است که فرزند داشته باشد پس برگها گره داخلی نیستند. زیر درخت بخشی از درخت است که خود یک درخت کامل را تشکیل می‌دهد. هر گره در درخت T با تمام گره‌های زیر آن زیر درخت درخت T را تشکیل می‌دهد. زیر درخت متناظر با گره ریشه درخت اصلی است. زیر درخت متناظر با بقیهٔ رئوس زیر درخت سره گفته می‌شود. درخت‌ها دو نوع اصلی هستند. درخت بازگشتی یا درخت نامرتب درختی است که فرزندان هر رأس ترتیب خاصی ندارند و درخت مرتب درختی است که در آن ترتیب خاصی اعمال می‌شود. برای مثال می‌توان به هر رأس عددی طبیعی مربوط کرد. هر عضو در درخت دارای یک لیست از کلیدها است. کلیدها مسئولیت جداسازی اطلاعات را هنگام اضافه‌شدن آن‌ها به درخت دارند که در نتیجه تعداد کلیدها یکی کمتر از تعداد فرزندان است. برای مثال فرض کنید یک عضو دارای کلید هایformula_1 باشد. در این صورت این عضو دارای حداکثر n+1 فرزند است که چپ‌ترین فرزند آن مقدار کمتر مساوی با formula_2 و فرزند دوم آن مقدار کمتر مساوی با formula_3 و بیشتر از formula_2 دارد و به همین ترتیب فرزند i-ام مقداری بزگتر از formula_5 و کمتر مساوی با formula_6 دارد. حال در اینجا با استفاده از زبان برنامه‌نویسی پایتون یک کلاس برای اعضا می‌نویسیم. class Node: اضافه کردن یک عضو جدید شبیه به درخت دودویی است.فرض کنید می خواهید مقدار c را به درخت اضافه کنید.ابتدا ریشه را در نظر می‌گیریم.بعد با مقایسع کردن مقدار c با کلیدها زیر درختی که این مقدار باید به ان اضافه شود را پیدا می‌کنیم.این روند را ادامه می‌دهیم تا به یک راس ایجاد نشده برسیم سپس با اضافه‌کردن ان مقدار c را به درخت اضافه میکنیم. حذف یک عنصر هم دقیقاً شبیه درخت دودویی است.ابتدا باید راسی را که می خواهیم حذف کنیم پیدا کنیم که این کار همانند زمانی است که می خواستیم هنگام درج راس خالی مناسب را پیدا کنیم.بعد از پیدا کردن راس مناسب کافی است مانند درخت دودویی ، بزرگ‌ترین راس در زیردرخت ان را در ان جایگزین کنیم و ان راس را حذف کنیم.اگر فرض کنیم درخت متوازن است در نتیجه هزینه درج و حذف هم برابر است با پیدا کردن راس مناسب که برابر با ارتفاع درخت که formula_7 است می‌باشد . در بالا هزینه‌های زمانی فرکتال و درخت رو با هم مقایسه کردیم. اما این دو از نظر مقدار حافظه بسیار متفاوت هستند. در درخت هر عضو B بچه دارد و در نتیجه هر راس حافظه‌ای از مرتبه B دارد. اما در فرکتال هر عضو دارای formula_8 فرزند و formula_8 مقدار است و در نتیجه مرتبه حافظه مورد نیاز هر راس formula_8 است. از طرفی اگر N مقدار را در درخت و فرکتال ذخیره کنیم، درخت دارای N راس و فرکتال دارای formula_11 راس است. در نتیجه حافظه مورد نیاز درخت B برابر فرکتال است.
یکی دیگر از مزیت‌های فرکتال زمانی است که از این الگوریتم در حافظه دیسک‌ها استفاده شود. فرض کنید اطلاعات را در دو دیسک ذخیره کرده‌اید که یکی با الگوریتم درخت و دیگری با فرکتال کار می‌کند. در این صورت می‌دانیم هزینه دسترسی و خواندن اطلاعات از دیسک بسیار زیاد است و می‌خواهیم تا جای ممکن دسترسی به دیسک را کاهش دهیم. در این صورت در دیسکی که با الگوریتم درخت کار می‌کند برای خواندن یک مقدار باید ابتدا ان را جستجو کرد و سپس آن را از دیسک خواند و به حافظه نهان آورد. حال برای مقدار بعدی دوباره باید همین کار را انجام داد. اما اگر دیسک با الگوریتم فرکتال کار کند بعد از پیدا کردن مقدار می‌توان کل حافظه نهان راس را به حافظه نهان آورد و طبق اصل محلی دسترسی‌ها، تعداد دسترسی‌ها به حافظه کمتر می‌شود و مخصوصاً زمانی که بخواهیم عمل نوشتن در حافظه انجام دهیم این اختلاف محسوس تر است.