Skip list คืออะไร และมันบรรลุการค้นหา O(log n) ได้อย่างไร

Question

Accepted Answer

**Skip list** คือรายการที่เชื่อมต่อแบบเรียงลำดับซึ่งขยายด้วยหลายระดับ **"express lane"** ระดับที่สูงกว่าข้ามโหนดจำนวนมาย ดังนั้นการค้นหาจึงลงและเลื่อนไปทางขวา บรรลุเวลาที่คาดหวัง **O(log n)** — เป็นทางเลือกแบบสุ่มตัวอย่างที่ง่ายกว่าต้นไม้ที่สมดุล ## โครงสร้าง ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` แต่ละโหนดจะได้รับการแต่งตั้งให้เป็นระดับที่สูงกว่าด้วยความน่าจะเป็น `p` (มักเป็น 0.5) ดังนั้นโดยเฉลี่ย แต่ละระดับจึงมีโหนดน้อยกว่า ลึกกว่า ## การค้นหา ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## ความซับซ้อน | การดำเนินการ | ที่คาดหวัง | พื้นที่ | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## ความยุติธรรมต่อต้นไม้ที่สมดุล - **จุดแข็ง:** ง่ายมากในการนำไปใช้งานกว่า red-black/AVL ไม่มีการหมุนเวียน เวอร์ชันพร้อมกันที่ง่าย (ใช้ใน Redis sorted sets, Java `ConcurrentSkipListMap`). - **จุดอ่อน:** การรับประกันความน่าจะเป็น (ไม่ใช่กรณีที่เลวร้ายที่สุด) ตัวชี้เพิ่มเติมต่อโหนด ## ทำไมถึงสำคัญ Skip lists ส่งมอบการดำเนินการตามลำดับแบบต้นไม้ O(log n) ด้วยโค้ดที่น้อยกว่ามากและความเป็นพร้อมกันที่ปราศจากการล็อก ซึ่งเป็นเหตุผลที่ระบบจริงเช่น Redis จึงเลือกพวกเขา พวกเขาเป็นตัวอย่างที่ยอดเยี่ยมของการใช้ **การสุ่ม** เพื่อแทนที่ตรรกะการสมดุลแบบกำหนดขึ้นที่ซับซ้อน