ডেটা স্ট্রাকচরে স্প্লে ট্রির অপ্টিম্যালিটি

ডাইনামিক অপ্টিম্যালিটি কনজেকচার (Dynamic optimality conjecture)

স্প্লে ট্রির প্রুভড পারফরম্যান্স গ্যারান্টির পাশাপাশি একটি অনপ্রুভড কনজেকচার আছে বড় আগ্রহের। ডাইনামিক অপ্টিম্যালিটি কনজেকচার এই কনজেকচারকে ডেনোট করে। যেকোনো বাইনারি সার্চ ট্রি অ্যালগরিদম যেন B একটি এলিমেন্ট y অ্যাক্সেস করে রুট থেকে y-র পাথ ট্রভার্স করে d(y)+1 কস্টে, এবং অ্যাক্সেসের মাঝপথে ট্রিতে যেকোনো রোটেশন করতে পারে ১ প্রতি রোটেশনের কস্টে। B(s) হোক B-এর কস্ট s সিকোয়েন্স অফ অ্যাক্সেস পারফর্ম করতে। তবে স্প্লে ট্রির কস্ট সেইম অ্যাক্সেস পারফর্ম করতে O[n+B(s)]।

ডাইনামিক অপ্টিম্যালিটি কনজেকচারের অনেক কোরোলারি আছে যা অনপ্রুভড আছে

ট্রভার্সাল কনজেকচার (Traversal Conjecture) একই এলিমেন্ট দুটি স্প্লে ট্রি t1 এবং t2-এ কন্টেইন করা থাকে। t2-এ প্রি-অর্ডার (অর্থাৎ ডেপথ ফার্স্ট সার্চ অর্ডার) এলিমেন্ট ভিজিট করে প্রাপ্ত সিকোয়েন্সকে s ধরা হয়। t1-এ s সিকোয়েন্স অফ অ্যাক্সেস পারফর্ম করার মোট কস্ট O(n)।

ডিক কনজেকচার (Deque Conjecture) p ডাবল-এন্ডেড কিউ অপারেশন (পুশ, পপ, ইনজেক্ট, ইজেক্ট) এর একটি সিকোয়েন্স s ধরা হয়। তবে একটি স্প্লে ট্রিতে s সিকোয়েন্স পারফর্ম করার কস্ট O(p+n)।

স্প্লিট কনজেকচার (Split Conjecture) স্প্লে ট্রির এলিমেন্টের যেকোনো পারমুটেশন s ধরা হয়। তবে এলিমেন্টগুলো s অর্ডারে ডিলিট করার কস্ট O(n)।