ی-فست تری: ساختار داده‌ای برای ذخیره اعداد صحیح

ی-فست تری چیست؟

ی-فست تری یک ساختار داده برای ذخیره اعداد صحیح در محدوده مشخص است. این ساختار توسط دن ویلارد در سال ۱۹۸۲ پیشنهاد شد تا فضای ذخیره‌سازی تری ایکس-فاست را کاهش دهد. ی-فست تری از دو بخش تشکیل شده است: نیمه بالایی که یک تری ایکس-فاست است و نیمه پایینی که شامل چندین درخت باینری متعادل است.

ساختار ی-فست تری

کلیدهای داده‌ها به گروه‌های O(log M) تقسیم می‌شوند و برای هر گروه یک درخت جستجوی باینری متعادل ایجاد می‌شود. برای هر درخت، یک نماینده انتخاب می‌شود که در تری ایکس-فاست ذخیره می‌گردد. این نمایندگان لزوماً جزئی از درخت مرتبط نیستند، اما باید شرایط خاصی را برآورده کنند.

عملیات ی-فست تری

ی-فست تری عملیات‌هایی مانند جستجو، پیدا کردن جانشین و پیشرو، درج و حذف را پشتیبانی می‌کند. این عملیات‌ها با پیچیدگی زمانی O(log log M) انجام می‌شوند.

• جستجو: با استفاده از نمایندگان در تری ایکس-فاست و جستجو در درخت‌های باینری متعادل.
• درج: با تعیین درخت مناسب و تقسیم درخت در صورت لزوم.
• حذف: با پیدا کردن کلید و ادغام درخت‌ها در صورت لزوم.