Virtual Tree Overview
ใน Virtual Tree: Edges บางส่วนเป็น Solid (แท้) บางส่วนเป็น Dashed (ขีด)
Splaying ปกติทำใน Solid Trees เท่านั้น
Algorithm: Splay(y) - 3 Passes
Pass 1: Walk Up + Splay in Solid Subtrees Only
- เริ่มจาก Node y
- Splay ภายใน Solid Subtrees เท่านั้น
- จบ Pass 1: Path จาก y ถึง Root กลายเป็น Dashed ทั้งหมด
Pass 2: Walk Up + Splice at Proper Ancestors
- เดินขึ้นจาก y, Splice ที่ Proper Ancestor ทุกตัว
- จบ Pass 2: Path จาก y ถึง Root กลายเป็น Solid ทั้งหมด
- ยกเว้น: y และ Children เดิมของ y (ก่อน Pass 1) กลายเป็น Left Children
Pass 3: Walk Up + Normal Splay
- เดินขึ้นจาก y ถึง Root, Splying แบบปกติ
- Result: y กลายเป็น Root ของ Tree
ตัวอย่าง: Huffman Coding บน Virtual Tree
Letter Frequency Table:
| Letter | z | k | m | c | u | d | l | e |
| Frequency | 2 | 7 | 24 | 32 | 37 | 42 | 42 | 120 |
Huffman Codes:
| Letter | Freq | Code | Bits |
|---|---|---|---|
| e | 120 | 0 | 1 |
| d | 42 | 101 | 3 |
| l | 42 | 110 | 3 |
| u | 37 | 100 | 3 |
| c | 32 | 1110 | 4 |
| m | 24 | 11111 | 5 |
| k | 7 | 111101 | 6 |
| z | 2 | 111100 | 6 |
สรุป
Splay ใน Virtual Tree ใช้ 3 Passes เพื่อย้าย Node ให้กลายเป็น Root พร้อมรักษา Solid/Dashed Structure ใช้ใน Dynamic Trees, Link-Cut Trees, และ Huffman Coding Optimization
