Dynamic Finger Search Data Structure Requirements
- Finger Searches + Insert/Delete ที่ Position ที่ Finger ระบุ
- Finger Search Trees = B-tree Variant: Finger Search O(log d), Updates O(1) (O(1) Movable Fingers)
- Traverse Finger d Positions = O(log d) Time
Construction Categories
| Category | ลักษณะ |
|---|---|
| Fixed Constant Fingers / Amortized Updates | AVL, Red-Black Trees เป็น Base |
| Arbitrary Fingers + Worst-case Updates | Constructions รองรับได้ |
| O(1) Updates แต่ Search O(log n) Only | ไม่ใช่ True Finger Search |
| O(log d) Search + O(logd n) Insert/Delete | Trade-off |
| Worst-case O(1) Insert + O(logd n) Delete | Finger Search Trees |
Space-Efficient Alternative: Single Finger + Hand Structure
แทน Level Links + Parent Pointers → ใช้ Hand = O(log n) Space Data Structure สำหรับ Finger เดียว
Performance = เท่า (2,4)-Trees
Splay Trees as Finger Search Trees
- Splay Trees = Self-Adjusting BST: Search/Insert/Delete Amortized O(log n)
- Given O(n) Initialization: Amortized Cost ของ Access ที่ Distance d จาก Previous Access = O(log d)
- Accesses = Searches, Insertions, Deletions
- Constraint: 1 Finger เท่านั้น (ชี้ไป Last Accessed Element เสมอ)
Pointer Machine vs RAM Model
- Pointer Machine: Element Operations = Compare เท่านั้น → Constructions ทั้งหมด Apply ได้
- RAM Model: Finger Search Tree พัฒนาได้ → Constant Update + O(log d) Search
โดย Tabulate Small Tree Structures, ใช้ Compare เท่านั้น
