डायनामिक इष्टतमता अनुमान (Dynamic Optimality Conjecture)
स्प्ले ट्रीज़ के लिए सिद्ध प्रदर्शन गारंटी के अलावा एक अप्रमाणित अनुमान (Unproven Conjecture) है जिसमें बहुत रुचि है। डायनामिक इष्टतमता अनुमान इस अनुमान को दर्शाता है। मान लीजिए कोई भी बाइनरी सर्च ट्री एल्गोरिदम जैसे B एक एलिमेंट y को रूट से y तक का पथ पार करके एक्सेस करता है जिसकी लागत d(y)+1 है, और एक्सेस के बीच ट्री में कोई भी रोटेशन 1 प्रति रोटेशन की लागत पर कर सकता है। मान लीजिए B(s) एक्सेस के अनुक्रम s को करने के लिए B की लागत है। तब एक स्प्ले ट्री द्वारा उन्हीं एक्सेस को करने की लागत O[n + B(s)] है।
डायनामिक इष्टतमता अनुमान के कई उपपरिणाम (Corollaries) हैं जो अप्रमाणित हैं
ट्रैवर्सल अनुमान (Traversal Conjecture) मान लीजिए दो स्प्ले ट्री t1 और t2 में समान एलिमेंट हैं। t2 में प्रीऑर्डर (यानी डेप्थ फर्स्ट सर्च ऑर्डर) में एलिमेंट्स को विज़िट करके प्राप्त अनुक्रम को s माना जाता है। t1 पर एक्सेस के अनुक्रम s को करने की कुल लागत O(n) है।
डेक अनुमान (Deque Conjecture) मान लीजिए p डबल-एंडेड क्यू ऑपरेशन (पुश, पॉप, इंजेक्ट, इजेक्ट) का अनुक्रम s है। तब स्प्ले ट्री पर s अनुक्रम को करने की लागत O(p + n) है।
स्प्लिट अनुमान (Split Conjecture) मान लीजिए s स्प्ले ट्री के एलिमेंट्स का कोई भी क्रमपरिवर्तन (Permutation) है। तब एलिमेंट्स को क्रम s में हटाने की लागत O(n) है।
