Level Linked (2,4)-Trees ในโครงสร้างข้อมูล

Level Linked (2,4)-Trees

(2,4)-Tree = Height-Balanced Search Tree
- Leaves ทุกตัว Depth เท่ากัน
- Internal Nodes Degree = 2, 3, หรือ 4
- Elements เก็บที่ Leaves, Internal Keys = Search Guides
- Height = O(log n), Search = O(log n)

Important Property: Insert/Delete by Finger = Amortized O(1) (ไม่ใช่ (2,3)-trees ที่มี Sequences ใช้ Θ(m log m))
Split/Join: Amortized O(log min(m₁, m₂))

Finger Search ด้วย Level Links

Augment: Nodes ที่ Depth เท่ากัน → Linked ใน Doubly Linked List (Level Links)
Level Links 易于 Maintain ระหว่าง Insert/Delete/Split/Join

Finger Search Algorithm (X → Y, สมมติ Y อยู่ขวา X)

1. Walk Up จาก X ไป Root พร้อมตรวจสอบ Node V และ Right Neighbour ของ V
2. หยุดเมื่อ Y อยู่ใน Subtree ของ V หรือ Right Neighbour ของ V
3. เริ่ม Downward Search สูงสุด 2 ครั้ง จาก V และ/หรือ Right Neighbour

Thick Lines ในรูป = Pointers ที่ Follow ระหว่าง Finger Search (j → t)

Why O(log d)?

ขึ้นไป Parent ของ V → Y อยู่ขวา Leftmost Subtree ของ V's Right Neighbour
→ d อย่างน้อย Exponential ใน Height ที่ขึ้นไปแล้ว

Generalization: Level Linked (a,b)-Trees

ใช้ได้กับ (a,b)-Trees ทั่วไป (b ≥ 2a)
External Memory: เลือก a = 2b, b ให้ Internal Node Fit ใน Block
→ Finger Search Trees ใน External Memory:
- Insert/Delete: O(1) Memory Transfers
- Finger Search: O(log_b n) Memory Transfers