یک درختیپ داده‌ساختاری است درختی که هر گره در آن دارای دو کلید $k$ و $p$ می‌باشد. در واقع این درخت یک درخت دودویی است که بر اساس کلید $k$ خواص یک درخت دودویی جستجو را دارد و براساس کلید دیگر یک هیپ است. در این سوال فرض می کنیم که درختیپمان یک هیپ بیشینه است. یعنی مقدار $p$ ریشه مقدار بیشینه را دارد. دقت کنید شرط تقریبا کامل بودن درخت هیپ در این داده‌ساختار لزوما رعایت نمی‌شود. اصولا از این داده‌ساختار برای ساختن درخت‌های دودویی جستجو با ارتفاع $Ο(\log n)$ استفاده می‌شود. در واقع کلیدهای $p$ ترتیب وارد کردن عناصر را درون یک درخت دودویی جستجو مشخص می‌کنند. فرض ما در این سوال این است که درختیپ ها ارتفاع متوسط $Θ(\log n)$ دارند. شما در این سوال می‌توانید یکی از دو قسمت زیر را انتخاب کرده و به آن پاسخ دهید:

1. رویه insert یک عنصر $x$ با دو کلید $k$ و $p$ را پیاده‌سازی کنید (شبه‌کد) و همچنین درباره عملکرد شبه‌کدتان توضیح دهید. الگوریتم پیاده‌سازی شده در حالت متوسط باید از مرتبه زمانی $\Theta(\log n)$ باشد.
2. رویه ادغام یا merge دو درختیپ $T_1$ و $T_2$ را با مرتبه زمانی متوسط $O(n)$ پیاده‌سازی کنید (شبه‌کد). $n$ را مجموع رووس درون $T_1$ و $T_2$ در نظر بگیرید. در مورد نحوه عملکرد و درستی شبه‌کدتان توضیح دهید.

• سوال بعد
• سوال قبل