درخت تی

اگرچه به نظر می‌رسد که درختان T در پایگاه‌های داده‌های حافظه اصلی کاربردهای فراوانی دارند اما تحقیقات اخیر نشان داده‌اند که آن‌ها بهتر از درختان B در سخت افزارهای مدرن عمل نمی‌کنند:

مقاله (Rao, Jun; Kenneth A. Ross 1999)؛ با نام "مخزن نمایه‌سازی آگاهانه برای پشتیبانی از تصمیم‌گیری در حافظه اصلی". مجموعه مقالات بیست و پنجمین کنفرانس بین‌المللی در زمینه پایگاه‌های داده‌های بسیار بزرگ (VLDB 1999) . مورگان کافمان؛ صفحات 78 تا 89.

مقاله (Kim, Kyungwha; Junho Shim & Ig-hoon Lee 2007)؛ با عنوان مخزن درختان آگاهانه: آن‌ها چگونه در ریزپردازنده‌های کالای فعلی کار می‌کنند؟ از مجموعه مقالات پنجمین کنفرانس بین‌المللی علوم محاسبات و کاربردهای آن (ICCSA 2007). اسپرینگر؛ صفحات 189 تا 200. DOI: 10.1007/978-3-540-74472-6_15 .

به نظر می‌رسد که علت اصلی فرضیات سنتی در خصوص منابع حافظه باشد که دارای هزینه‌های یکنواخت هستند اما فعلاً و با توجه به مسئله شکاف سرعت فعلی بین دسترسی به مخزن و دسترسی به حافظه اصلی معتبر شناخته نمی‌شوند.

یک درخت T دارای گره‌هایی است که معمولاً شامل یک اشاره گر به گره والد؛ گره‌های چپ و راست فرزند هستند و همچنین یک آرایه منظم از اشاره گرهای داده‌ها و همچنین کنترل داده‌های اضافی در اختیار دارند. گره‌هایی که دارای دو درخت فرعی باشند به نام گره‌های داخلی شناخته شده و گره‌هایی که دارای درختان فرعی نباشند را گره‌های برگ می نامند. گره‌هایی که فقط یک درخت فرعی داشته باشند را گره‌های نیم برگ می نامند. گرهی را گره محدود به یک ارزش می نامند که آن ارزش بین ارزش‌های حداقل و حداکثر آن گره قرار داشته باشد.

ارزش‌های محدود شده هر گره داخلی می‌تواند دارای گره‌های برگ یا نیم برگ باشد که شامل سلف ارزش‌های داده‌های کوچکتر هستند (به نام بزرگترین کران پائین) یا می‌تواند شامل جانشین با ارزش‌های داده‌های بزرگتر از خودش باشد (به نام حداقل کران بالا). گره‌های برگ و نیم برگ می‌توانند شامل تعدادی از عناصر داده‌ها باشد که از 1 تا حداکثر سایز آرایه داده‌ها باشد. گره‌های داخلی تلاش می‌کنند تا فضای اشغال شده آن‌ها بین اعداد حداقل و حداکثر از عناصر باقی بماند.

این بخش نیاز به گسترش دارد (ژوئن 2008)

جستجو

• جستجو از گره ریشه آغاز می‌شود.
• اگر گره فعلی یک گره محدود شده برای ارزش جستجو باشد؛ پس جستجو در آرایه داده‌های همان گره صورت می‌گیرد. اگر ارزش مورد نظر در آرایه داده‌ها موجود نباشد؛ جستجو با شکست رو به رو می‌شود.
• اگر ارزش جستجو کمتر از ارزش حداقل گره مورد نظر باشد؛ پس جستجو در درخت فرعی سمت چپ انجام می‌شود. اگر هیچ درخت فرعی در سمت چپ وجود نداشته باشد؛ جستجو با شکست مواجه خواهد شد.
• اگر ارزش جستجو بالاتر از ارزش حداکثر در گره مورد نظر باشد؛ جستجو در درخت فرعی سمت راست ادامه می یابد. اگر درخت فرعی سمت راست نداشته باشیم؛ جستجو با شکست مواجه می‌شود.

وارد کردن

• جستجو در یک گره محدود برای یک ارزش جدید. اگر چنین گرهی وجود داشته باشد؛ پس:
  • کنترل می‌شود که آیا هنوز فضای کافی برای آرایه داده‌ها وجود دارد یا خیر؛ اگر فضا کافی باشد پس ارزش جدید وارد شده و پایان
  • اگر فضایی موجود نباشد پس ارزش حداقل از آرایه داده‌های گره برداشته شده و یک ارزش جدید وارد می‌شود. اکنون که گره بیشترین حد پائینی را دارد؛ ارزش جدید وارد می‌شود. اگر ارزش حداقل برداشته شده با محل جدید تناسب کافی داشته باشد به عنوان یک ارزش حداکثر جدید به آن گره افزوده می گرددو در غیر این صورت یک گره فرعی جدید در سمت چپ این گره ایجاد می‌شود.
• اگر هیچ گره محدودی یافت نشد؛ پس ارزش جدید در آخرین گره یافت شده که با آن تناسب داشته باشد؛ وارد می‌شود. در این صورت ارزش جدید به عنوان ارزش حداقل جدید یا ارزش حداکثر جدید معرفی می‌شود. اگر ارزش موردنظر با هیچیک تناسب نداشته باشد؛ یک درخت فرعی جدید در سمت راست یا چپ ایجاد می‌شود.

هر زمان که یک گره جدیدی افزوده می‌شود؛ درخت باید دوباره تنظیم گردد؛ به شرح ذیل.

حذف

• جستجو برای گره محدود به ارزش باید حذف گردد. اگر هیچ گره محدودی یافت نشود؛ پایان اعلام می‌شود.
• اگر گره محدود دارای هیچ ارزشی نباشد؛ پایان اعلام می‌شود.
• ارزش از آرایه داده‌های گره حذف می‌شود.

اکنون باید نوع گره را تشخیص بدهیم:

• گره داخلی:

اگر آرایه کنونی داده‌های گره کمتر از تعداد عناصر حداقل باشد؛ پس ارزش بزرگترین حد پائینی این گره به ارزش داده‌های آن منتقل می‌شود. در ادامه یکی از دو مرحله ذیل برای گره برگ یا نیم برگ که ارزش آن برداشته شده باشد انجام می دهیم.

• گره برگ:

اگر این ارزش تنها عنصر موجود در آرایه داده‌ها باشد؛ پس گره به‌طور کامل حذف می‌شود. در صورت لزوم باید درخت را دوباره تنظیم کنید.

• گره نیم برگ:

اگر آرایه داده‌های گره را بتوان با آرایه‌های داده‌های برگ‌هایش ادغام کرد به‌صورتی که هیچ مازادی مشاهده نشود؛ این کار را انجام داده و گره برگ را بر می دارید. در صورت لزوم باید درخت را دوباره تنظیم کنید.

چرخش و تعادل

این بخش نیاز به توسعه دارد (ژوئن 2008) یک درخت T بر روی یک درخت جستجوی باینری با تعادل خودبخودی اجرا می‌شود. به‌طور خاص؛ مقاله Lehman & Carey توصیف‌کننده یک درخت T متعادل همانند درخت AVL است: زمانی این درخت از تعادل خارج می‌شود که درخت‌های فرزندان گره از نظر ارتفاع حداقل به اندازه دو سطح متفاوت شده باشند. این مسئله زمانی روی می‌دهد که حذف یا اضافه کردن یک گره روی داده باشد. پس از افزودن یا حذف کردن باید درخت را از برگ تا ریشه اسکن کنید. اگر عدم تعادلی مشاهده کردید؛ باید یک چرخش درخت یا یک جفت چرخش انجام دهید تا تعادل کل درخت تضمین گردد.

اگر چرخش ناشی از این باشد که یک گره داخلی دارای تعداد آیتم‌های کمتری از تعداد حداقل مجاز باشد؛ آیتم‌های موجود در گره‌های فرزند جدید به داخل گره داخلی منتقل می‌شوند.

این بخش خالی است. شما می‌توانید برای پر کردن آن کمک کنید.

• درخت (تئوری گراف)
• درخت (تئوری مجموعه)
• ساختار درخت
• درخت نمایی

درختان دیگر

• درخت B(درخت 3-2 ؛ درخت 4-3-2 ؛ درخت B+؛ درخت B* ؛ درخت UB)
• الگوریتم DSW
• درخت رقصنده
• درخت ائتلاف
• درخت kd
• درخت هشت تایی
• درخت چهارتایی
• درخت R
• درخت T
• هرم T
• درختان تاپ