Finger Search ใน Skip Lists
จาก Node ที่มี Element b → Finger Search หา Element a
a < b → Search ย้อนหลัง (Backward)
a > b → Search ไปข้างหน้า (Forward)
Backward Case = Symmetric กับ Normal Search
Forward Case = ซับซ้อนกว่า (Sentinel ที่ Start เป็น Tallest Node ปกติ → Fast)
แต่ Finger อาจอยู่ที่ Height 1 Node → อาจต้อง "Climb" ขึ้น (ไม่เกิดใน Normal Search)
Properties ของ Skip Lists
- Expected Linear Space
- Expected O(log n) Levels
- Search: Expected O(log n) Time
- Insert/Delete at Given Position: Expected O(1) Time
Finger Search Implementation (Expected O(log d))
d = Distance ระหว่าง Finger และ Target
Backward Finger Search
- เก็บ Finger Data Structure: O(log n) Space, แต่ละ Level i เก็บ Pointer ไป Node ซ้ายของ Finger ที่ Level i Pointer ชี้ไป Finger หรือ Node ขวาของ Finger
- Move Finger → Update Pointer List
- Search: หา Lowest Node ใน Finger Structure ที่อยู่ซ้ายของ Search Key y (พิจารณา Level เรียงเพิ่ม) → Downward Search แบบ Standard Skip List
Forward Finger Search
ซับซ้อนกว่า เนื่องจากอาจต้อง Climb แต่ยัง Achieve O(log d) Expected Time ได้
สรุป
Skip Lists = Probabilistic Alternative ของ Balanced BSTs
Finger Search ได้ O(log d) โดยไม่เปลี่ยนโครงสร้างหลัก
ใช้ Randomization ทำให้ Update Operations เรียบง่ายและมีประสิทธิภาพ
