موضوع مقاله: درخت تی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت تی | مقدمه: یک درخت T عبارتست از یک ساختار داده‌های درختی به صورت فهرست متعادل بهینه‌سازی شده که در آن می‌توان هم فهرست و هم داده‌های واقعی را به‌طور کامل در حافظه نگهداری کرد؛ همانطور که درخت B یک ساختار شاخص بهینه‌سازی شده برای ذخیره بر روی دستگاه‌های ذخیره ساز ثانویه مثل هارد دیسک می‌باشد. | ## بخش 1: درخت تی | درخت T در جستجوی مزایای عملکرد در ساختارهای درختی موجود در حافظه می‌باشد مثل درخت‌های AVL اما در عین حال از فضاهای عظیم ذخیره‌سازی در بالای سر ؛ که در این نوع درختان بسیار رایج است ؛ هم اجتناب می‌کند. درختان T نسخه برداری از زمینه‌های داده‌های نمایه شده در گره‌های درخت شاخص را انجام نمی‌دهند. بلکه آن‌ها از این واقعیت سود می برند که داده‌های واقعی همیشه به همراه فهرست داخل حافظه اصلی وجود دارند بنابراین آن‌ها فقط دارای اشاره گرهایی برای اشاره به رشته‌های داده‌های واقعی هستند. حرف “T” در درخت T به شکل ساختار گره داده‌ها اشاره دارد که در مقاله اصلی و برای اولین بار به این نوع شاخص اشاره شده‌است. عملکرد اگرچه به نظر می‌رسد که درختان T در پایگاه‌های داده‌های حافظه اصلی کاربردهای فراوانی دارند اما تحقیقات اخیر نشان داده‌اند که آن‌ها بهتر از درختان B در سخت افزارهای مدرن عمل نمی‌کنند: مقاله (Rao, Jun; Kenneth A. Ross 1999)؛ با نام "مخزن نمایه‌سازی آگاهانه برای پشتیبانی از تصمیم‌گیری در حافظه اصلی". مجموعه مقالات بیست و پنجمین کنفرانس بین‌المللی در زمینه پایگاه‌های داده‌های بسیار بزرگ (VLDB 1999) . از مجموعه مقالات پنجمین کنفرانس بین‌المللی علوم محاسبات و کاربردهای آن (ICCSA 2007). یک درخت T دارای گره‌هایی است که معمولاً شامل یک اشاره گر به گره والد؛ گره‌های چپ و راست فرزند هستند و همچنین یک آرایه منظم از اشاره گرهای داده‌ها و همچنین کنترل داده‌های اضافی در اختیار دارند. گره‌هایی که دارای دو درخت فرعی باشند به نام گره‌های داخلی شناخته شده و گره‌هایی که دارای درختان فرعی نباشند را گره‌های برگ می نامند. | ## بخش 2: درخت تی | گرهی را گره محدود به یک ارزش می نامند که آن ارزش بین ارزش‌های حداقل و حداکثر آن گره قرار داشته باشد. ارزش‌های محدود شده هر گره داخلی می‌تواند دارای گره‌های برگ یا نیم برگ باشد که شامل سلف ارزش‌های داده‌های کوچکتر هستند (به نام بزرگترین کران پائین) یا می‌تواند شامل جانشین با ارزش‌های داده‌های بزرگتر از خودش باشد (به نام حداقل کران بالا). گره‌های برگ و نیم برگ می‌توانند شامل تعدادی از عناصر داده‌ها باشد که از 1 تا حداکثر سایز آرایه داده‌ها باشد. گره‌های داخلی تلاش می‌کنند تا فضای اشغال شده آن‌ها بین اعداد حداقل و حداکثر از عناصر باقی بماند. الگوریتم ها این بخش نیاز به گسترش دارد (ژوئن 2008) جستجو جستجو از گره ریشه آغاز می‌شود. اگر گره فعلی یک گره محدود شده برای ارزش جستجو باشد؛ پس جستجو در آرایه داده‌های همان گره صورت می‌گیرد. اگر ارزش جستجو کمتر از ارزش حداقل گره مورد نظر باشد؛ پس جستجو در درخت فرعی سمت چپ انجام می‌شود. اگر ارزش جستجو بالاتر از ارزش حداکثر در گره مورد نظر باشد؛ جستجو در درخت فرعی سمت راست ادامه می یابد. اگر چنین گرهی وجود داشته باشد؛ پس: کنترل می‌شود که آیا هنوز فضای کافی برای آرایه داده‌ها وجود دارد یا خیر؛ اگر فضا کافی باشد پس ارزش جدید وارد شده و پایان اگر فضایی موجود نباشد پس ارزش حداقل از آرایه داده‌های گره برداشته شده و یک ارزش جدید وارد می‌شود. اگر ارزش حداقل برداشته شده با محل جدید تناسب کافی داشته باشد به عنوان یک ارزش حداکثر جدید به آن گره افزوده می گرددو در غیر این صورت یک گره فرعی جدید در سمت چپ این گره ایجاد می‌شود. | ## بخش 3: درخت تی | اگر هیچ گره محدودی یافت نشد؛ پس ارزش جدید در آخرین گره یافت شده که با آن تناسب داشته باشد؛ وارد می‌شود. در این صورت ارزش جدید به عنوان ارزش حداقل جدید یا ارزش حداکثر جدید معرفی می‌شود. اگر ارزش موردنظر با هیچیک تناسب نداشته باشد؛ یک درخت فرعی جدید در سمت راست یا چپ ایجاد می‌شود. اکنون باید نوع گره را تشخیص بدهیم: گره داخلی: اگر آرایه کنونی داده‌های گره کمتر از تعداد عناصر حداقل باشد؛ پس ارزش بزرگترین حد پائینی این گره به ارزش داده‌های آن منتقل می‌شود. در ادامه یکی از دو مرحله ذیل برای گره برگ یا نیم برگ که ارزش آن برداشته شده باشد انجام می دهیم. گره برگ: اگر این ارزش تنها عنصر موجود در آرایه داده‌ها باشد؛ پس گره به‌طور کامل حذف می‌شود. گره نیم برگ: اگر آرایه داده‌های گره را بتوان با آرایه‌های داده‌های برگ‌هایش ادغام کرد به‌صورتی که هیچ مازادی مشاهده نشود؛ این کار را انجام داده و گره برگ را بر می دارید. چرخش و تعادل این بخش نیاز به توسعه دارد (ژوئن 2008) یک درخت T بر روی یک درخت جستجوی باینری با تعادل خودبخودی اجرا می‌شود. به‌طور خاص؛ مقاله Lehman & Carey توصیف‌کننده یک درخت T متعادل همانند درخت AVL است: زمانی این درخت از تعادل خارج می‌شود که درخت‌های فرزندان گره از نظر ارتفاع حداقل به اندازه دو سطح متفاوت شده باشند. اگر عدم تعادلی مشاهده کردید؛ باید یک چرخش درخت یا یک جفت چرخش انجام دهید تا تعادل کل درخت تضمین گردد. | ## جمع‌بندی | اگر چرخش ناشی از این باشد که یک گره داخلی دارای تعداد آیتم‌های کمتری از تعداد حداقل مجاز باشد؛ آیتم‌های موجود در گره‌های فرزند جدید به داخل گره داخلی منتقل می‌شوند.