ডাইনামিক অপ্টিম্যালিটি অনুমান
স্প্লে গাছের জন্য প্রমাণিত কর্মক্ষমতা গ্যারান্টি ছাড়াও প্রচুর আগ্রহের সাথে একটি অপ্রমাণিত অনুমান রয়েছে। ডাইনামিক অপ্টিম্যালিটি অনুমান এই অনুমানকে বোঝায়। যেকোন বাইনারি সার্চ ট্রি অ্যালগরিদম যেমন B-কে d(y)+1 খরচে রুট থেকে y-এর পথ অতিক্রম করে একটি উপাদান y অ্যাক্সেস করতে দিন এবং অ্যাক্সেসের মধ্যে 1 প্রতি খরচে গাছে যেকোনো ঘূর্ণন ঘটাতে পারে ঘূর্ণন অ্যাক্সেসের ক্রম s সম্পাদন করার জন্য B-এর জন্য B(গুলি) খরচ হতে দিন। তারপর একই অ্যাক্সেসগুলি সম্পাদন করার জন্য একটি স্প্লে ট্রির খরচ হল O[n+B(s)]।
ডাইনামিক অপ্টিম্যালিটি অনুমানের অনেক সমষ্টি আছে যা অপ্রমাণিত রয়ে গেছে
ট্রাভার্সাল অনুমান এবং একই উপাদান দুটি স্প্লে ট্রি t1 এবং t2 দ্বারা ধারণ করে। প্রি-অর্ডারে (অর্থাৎ, গভীরতার প্রথম অনুসন্ধানের ক্রম) টি 2-এ উপাদানগুলি পরিদর্শন করে প্রাপ্ত ক্রমটি s হিসাবে ধরে নেওয়া হবে। T1-এ অ্যাক্সেসের ক্রম গুলি সম্পাদনের সম্পূর্ণ খরচ হল O(n)।
ডিক অনুমান এবং p ডবল-এন্ডেড কিউ অপারেশনের একটি ক্রম s (ধাক্কা, পপ, ইনজেক্ট, বের করা) সংজ্ঞায়িত করা হয়েছে। তারপর একটি স্প্লে ট্রিতে s ক্রম সম্পাদনের খরচ হল O(p+n)।
বিভক্ত অনুমান et s স্প্লে গাছের উপাদানগুলির যেকোন স্থানান্তর। তারপর ক্রম s-এর উপাদানগুলিকে মুছে ফেলার জন্য খরচ হল O(n)৷
৷