Randomized Alternatives to Deterministic Search Trees
2 ตัวเลือกหลัก: Treaps (Randomized BSTs) และ Skip Lists
ทั้งคู่ Elegant, Randomization ทำให้ Update Operations เรียบง่ายและมีประสิทธิภาพ
ทั้งคู่รองรับ Finger Search ใน Expected O(log d) Time (d = Distance)
Expectation = Over Random Choices ระหว่าง Construction
Skip Lists (รายละเอียดเพิ่มเติม)
Finger Search จาก b หา a: Continue Search จาก b
a < b → Backward (Symmetric to Normal)
a > b → Forward (ซับซ้อน: Finger อาจ Height 1 → ต้อง Climb)
แต่ยัง Achieve O(log d) Expected Time ได้
Treaps (Tree + Heap)
Treap = Randomized BST
Search = เหมือน BST ปกติ
Property: Expected Path Length ระหว่าง 2 Elements ระยะ d = O(log d)
Finger Search ใน Treap
- Climb จาก Node b ขึ้นหา Ancestor ของ a
- เจอ Ancestor → Normal BST Search ต่อจากนั้น
Problem: Check "Is Ancestor?" Non-trivial
Solution: Augment Tree รองรับ Ancestor Queries → Expected O(log d) Finger Search
สรุป
ทั้ง Skip Lists และ Treaps รองรับ Finger Search ได้ดีโดยไม่ต้องเปลี่ยน Core Structure
Randomization = Key to Simplicity + Efficiency
Expected O(log d) Finger Search, Expected O(log n) Normal Operations
