Static Finger Theorem
ให้ f เป็น Element เฉพาะ เรียกว่า Finger
Cost ของ Splaying Sequence ถูก Bound โดย:
O(m + n log n + Σⱼ log(|f - iⱼ| + 1))
โดย:
- m = จำนวน Update/Access Operations บน Tree ที่มี Nodes ≤ n
- n = จำนวน Nodes สูงสุด
- |f - i| = ระยะทางใน Symmetric Ordering ระหว่าง Finger f และ Item i
Observation
อย่างน้อยใน Amortized Sense: เวลาสำหรับ m Operations แรกบน Tree ที่ไม่เกิน n Nodes = เวลาของ Balanced BSTs (AVL, 2-3 Trees, etc.)
ความหมาย
- Finger Theorem บอกว่า Splay Trees ใช้เวลาใกล้เคียง Balanced BSTs แม้ไม่ Rebalance ทุกครั้ง
- Static Finger = Fixed Reference Point ตลอด Sequence
- Dynamic Finger Theorem (แยกต่างหาก) = Finger เคลื่อนที่ไปยัง Last Accessed Element
