Dynamic Optimality Conjecture (推测 动态最优性)
Selain Performance Guarantees ที่พิสูจน์แล้ว มี Unproven Conjecture ที่น่าสนใจมาก:
ให้ Binary Search Tree Algorithm ใดๆ (B) Access Element y โดย Traverse Path จาก Root → y Cost = d(y) + 1 และระหว่าง Accesses ทำ Rotations ได้ Cost = 1 ต่อ Rotation
B(s) = Cost ของ B สำหรับ Sequence s ของ Accesses
Conjecture: Cost ของ Splay Tree สำหรับ Accesses เดียวกัน = O[n + B(s)]
Corollaries (ยังไม่พิสูจน์)
1. Traversal Conjecture
Splay Trees t1, t2 มี Elements เหมือนกัน s = Preorder Traversal ของ t2
Cost ของ Sequence s บน t1 = O(n)
2. Deque Conjecture
s = Sequence ของ p Double-ended Queue Operations (push, pop, inject, eject)
Cost บน Splay Tree = O(p + n)
3. Split Conjecture
s = Permutation ใดๆ ของ Splay Tree Elements
Cost ของ Deletion ตามลำดับ s = O(n)
สรุป
Dynamic Optimality Conjecture = Splay Trees ใกล้เคียง Optimal BST สำหรับ Sequence ใดๆ
ยังเป็น Open Problem สำคัญใน Data Structures Research
ถ้าจริง → Splay Trees = Universally Optimal Self-Adjusting BST
