একটি সিমেট্রিক মিন-ম্যাক্স হিপ (SMMH) হলো একটি কমপ্লিট বাইনারি ট্রি যাতে রুট ছাড়া প্রতিটি নোডে ঠিক একটি এলিমেন্ট থাকে। একটি SMMH-এর রুট খালি থাকে এবং SMMH-তে মোট নোডের সংখ্যা m + 1, যেখানে m হলো এলিমেন্টের সংখ্যা।
y কে SMMH-এর যেকোনো নোড ধরি। elements(y) হলো y-রুট করা সাবট্রিতে উপস্থিত এলিমেন্টগুলো কিন্তু y-তে থাকা এলিমেন্ট (যদি থাকে) বাদ দিয়ে। ধরি elements(y) ≠ ∅। y নিচের বৈশিষ্ট্যগুলো পূরণ করে:
- y-এর বাম চাইল্ডে elements(y)-র মিনিমাম এলিমেন্ট থাকে।
- y-এর ডান চাইল্ডে (যদি থাকে) elements(y)-র ম্যাক্সিমাম এলিমেন্ট থাকে।
চিত্র ১ একটি উদাহরণ SMMH দেখায় যাতে ১২টি এলিমেন্ট রয়েছে।
যখন y ৮১ Élément-যুক্ত নোডকে নির্দেশ করে, elements(y) = {৭, ১৫, ৩১, ৪১}; y-এর বাম চাইল্ডে elements(y)-র মিনিমাম এলিমেন্ট ৬ থাকে; এবং y-এর ডান চাইল্ডে elements(y)-র ম্যাক্সিমাম এলিমেন্ট ৪১ থাকে। আমরা যাচাই করতে পারি যে এই SMMH-এর প্রতিটি নোড y উল্লিখিত বৈশিষ্ট্যগুলো পূরণ করে।
যেহেতু একটি SMMH একটি কমপ্লিট বাইনারি ট্রি, এটি একটি ইম্প্লিসিট ডেটা স্ট্রাকচার হিসেবে সংরক্ষিত হয় কমপ্লিট বাইনারি ট্রিকে অ্যারের মধ্যে ম্যাপ করার стандарт ম্যাপিং ব্যবহার করে। যখন m = ১, মিনিমাম এবং ম্যাক্সিমাম এলিমেন্ট একই থাকে এবং SMMH-এর রুটের বাম চাইল্ডে থাকে।
যখন m > ১, মিনিমাম এলিমেন্ট রুটের বাম চাইল্ডে থাকে এবং ম্যাক্সিমাম ডান চাইল্ডে। তাই getMin এবং getMax অপারেশন O(1) টাইম নেয়।
সহজে দেখা যায় যে একটি m + ১-নোড কমপ্লিট বাইনারি ট্রি যার রুট খালি এবং রুট ছাড়া প্রতিটি নোডে একটি এলিমেন্ট থাকলে, সেটি একটি SMMH হবে যদি এবং কেবল যদি নিচের শর্তগুলো সত্য হয়:
A1 - প্রতিটি নোড y যাতে ডান সিবলিং থাকে, y-তে থাকা এলিমেন্ট y-এর ডান সিবলিং-এর এলিমেন্ট থেকে ছোট বা সমান।
A2 - প্রতিটি নোড y যাতে গ্র্যান্ডপ্যারেন্ট থাকে, গ্র্যান্ডপ্যারেন্টের বাম চাইল্ডের এলিমেন্ট y-তে থাকা এলিমেন্ট থেকে ছোট বা সমান।
A3 - প্রতিটি নোড y যাতে গ্র্যান্ডপ্যারেন্ট থাকে, গ্র্যান্ডপ্যারেন্টের ডান চাইল্ডের এলিমেন্ট y-তে থাকা এলিমেন্ট থেকে বড় বা সমান।
লক্ষ্য করুন যে যদি বৈশিষ্ট্য A1 নোড y-এ সত্য হয়, তবে A2 এবং A3-র সর্বোচ্চ একটি y-এ ভাঙা হতে পারে। বৈশিষ্ট্য A1 থেকে A3 ব্যবহার করে আমরা সিম্পল অ্যালগরিদম পাই এলিমেন্ট ইনসার্ট এবং রিমুভ করার জন্য। এই অ্যালগরিদমগুলো মিন এবং ম্যাক্স হিপের সংশ্লিষ্ট অ্যালগরিদমের সিম্পল অ্যাডাপটেশন। তাদের কমপ্লেক্সিটি O(log m)।
এখানে, আমরা ইনসার্ট অপারেশন নির্দিষ্ট করছি। ধরুন আমরা চাই চিত্র ১-এর SMMH-তে ৩ ইনসার্ট করা। যেহেতু একটি SMMH একটি কমপ্লিট বাইনারি ট্রি, আমাদের SMMH-তে একটি নতুন নোড যোগ করতে হবে চিত্র ২-এ দেখানো পজিশনে; নতুন নোডটি B হিসেবে লেবেল করা হয়েছে।
আমাদের উদাহরণে, B একটি খালি নোড নির্দেশ করবে। এখন ৩টি B নোডে ইনসার্ট করা হয়েছে।
