ساختار داده Treap؛ ترکیبی هوشمندانه از درخت جستجوی دودویی و هیپ

ساختار داده Treap که نام آن از ترکیب دو واژه Tree و Heap گرفته شده است، یک ساختار داده پیشرفته است که توسط Raimund Siedel و Cecilia Aragon در سال ۱۹۸۹ معرفی شد. این ساختار هر گره را به شکل زوج مقادیر (X, Y) ذخیره می‌کند؛ به‌طوری‌که نسبت به مقادیر X مانند یک درخت جستجوی دودویی (BST) و نسبت به مقادیر Y (که به آن‌ها اولویت یا Priority گفته می‌شود) مانند یک هیپ دودویی (Binary Heap) عمل می‌کند.

چرا Treap اهمیت دارد؟

در درخت‌های جستجوی دودویی معمولی، اگر داده‌ها به‌صورت مرتب‌شده وارد شوند، ساختار درخت به شکل یک لیست پیوندی تخریب می‌شود و پیچیدگی زمانی عملیات اصلی به O(N) افت می‌کند. اما در Treap، مقادیر اولویت Y به‌صورت تصادفی تولید می‌شوند (به همین دلیل به آن Randomized Binary Search Tree هم می‌گویند). این انتخاب تصادفی تضمین می‌کند که درخت در حالت میانگین متوازن بماند و پیچیدگی زمانی عملیات روی آن برابر با O(log N) باشد.

علاوه بر این، Treap را می‌توان به‌راحتی روی صفحه مختصات کارتیسین جای داد، به همین دلیل به آن درخت کارتیسین (Cartesian Tree) نیز می‌گویند.

عملیات اصلی در Treap

این ساختار داده از مجموعه‌ای از عملیات کارآمد پشتیبانی می‌کند:

• درج Insert(X, Y) با پیچیدگی O(log N)
• جستجو Search(X) با پیچیدگی O(log N)
• حذف Erase(X) با پیچیدگی O(log N)
• ادغام دو درخت Union
• ساخت اولیه درخت Build

پیاده‌سازی با دو عملیات پایه‌ای: Split و Merge

پیاده‌سازی این ساختار معمولاً بر پایه دو عملگر کمکی انجام می‌شود:

1. عملگر Split: درخت T را بر اساس کلید X به دو زیردرخت L (کوچک‌تر یا مساوی) و R (بزرگ‌تر) با پیچیدگی O(log N) تفکیک می‌کند.
2. عملگر Merge: دو زیردرخت T1 و T2 را که از نظر کلید مرتب هستند، با حفظ شرط هیپ (اولویت Y) در O(log N) ترکیب می‌کند.

پیاده‌سازی گره در C++

struct item {
    int key, prior;
    item *l, *r;
    item () { }
    item (int key) : key(key), prior(rand()), l(NULL), r(NULL) { }
    item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item* pitem;

توسعه قابلیت‌ها: نگهداری اندازه زیردرخت‌ها

با افزودن یک فیلد cnt به ساختار گره، می‌توان قابلیت‌های جدیدی مثل پیدا کردن Kامین عنصر بزرگ یا شاخص یک عنصر در لیست مرتب را در زمان O(log N) پیاده‌سازی کرد. کافی است مقدار cnt را در پایان عملیات‌هایی مثل درج، حذف، تفکیک و ادغام به‌روزرسانی کنید.

ساخت خطی درخت

اگر یک لیست مرتب از کلیدها داشته باشیم، می‌توانیم به‌جای درج تک‌تک عناصر (که زمان O(N log N) می‌برد)، درخت را در حالت آفلاین و در زمان خطی O(N) با استفاده از رویکرد بازگشتی و تابع heapify بسازیم.

دیدگاه جامعه مهندسی نرم‌افزار در Hacker News

در بحث‌های هکرنیوز، توسعه‌دهندگان اشاره کرده‌اند که این پیاده‌سازی مشخصاً یک Treap بدون چرخش یا اصطلاحاً fhq treap است که در برنامه‌نویسی رقابتی بسیار محبوب است. در مقابل، مهندسان نرم‌افزار سنتی‌تر ممکن است بیشتر با نسخه چرخشی (Rotating Variant) این ساختار آشنا باشند.