Splay Tree คืออะไร?
Splay Tree = Self-Balancing Binary Search Tree ที่มีคุณสมบัติพิเศษ: Recently Accessed Elements เข้าถึงได้เร็วขึ้น
Basic Operations (Insert, Lookup, Remove): O(log n) Amortized Time
สำหรับ Non-random Sequences หลายแบบ Splay Trees ทำงานดีกว่า Search Trees อื่นๆ แม้รูปแบบ Sequence ไม่ทราบล่วงหน้า
ทุก Normal BST Operations รวมกับ 1 Basic Operation: Splaying
BST Property
Node a: Left Subtree = Keys < key(a), Right Subtree = Keys > key(a)
Splaying Process
- Search Query Item a เหมือน BST ปกติ (Compare → Left/Right Recurse)
- ดู Disjoint Pairs ของ Consecutive Ancestors ของ a:
- b = parent(a), c = parent(b)
- ทำ Rotations คู่หนึ่ง → a เข้าตำแหน่ง c
3 ประเภท Splay Steps
1. Zig Step (Terminal Case)
a มี Proper Ancestors จำนวนคี่ → Ancestor ที่เป็น Child ของ Root ต้องจัดการแยก
→ Rotate Edge ระหว่าง a และ Root
2. Zig-Zig Step
a และ b ทั้งคู่เป็น Left Children หรือทั้งคู่เป็น Right Children
→ Rotate (b, c) ก่อน แล้ว Rotate (a, b)
3. Zig-Zag Step
a เป็น Left Child, b เป็น Right Child (หรือ Vice Versa)
→ Rotate (a, b) ก่อน แล้ว Rotate (a, c)
สรุปผลของ Splaying
- Accessed Node ย้ายขึ้นมากลายเป็น Root
- Tree ค่อยๆ Balanced ขึ้น (Amortized)
- Locality of Reference: เข้าถึงซ้ำเร็วขึ้น
