Apa iku skip list lan sapira carane nggayuh panggolèkan O(log n)?

Question

IT Interview Practice · Accepted Answer

A **skip list** iku daftar pranala tertib sing ditambah karo multipel tingkat **"jalur cepat"**. Tingkat sing luwih dhuwur nyukupi akèh node, dadi panggolèkan mlumpat mudhun lan mlayu ing tengen, nggayuh wektu dikarepaken **O(log n)** — alternatif probabilistik sing luwih simpel lan menyang awak jurang berimbang. ## Struktur ```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) ``` Saben node ditinggikake menyang tingkat luwih dhuwur karo probabilitas `p` (asring 0.5), dadi rata-rata saben tingkat duwe setengah saka node ing sisih ngisor. ## Panggolèkan ```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 ``` ## Kompleksitas | Operasi | Dikarepaken | Ruang | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Trade-off lawan awak jurang berimbang - **Kekuwatan:** luwih gampang diimplementasi tinimbang red-black/AVL; tanpa puteran; versi konkuren gampang (digunakake ing Redis sorted sets, Java `ConcurrentSkipListMap`). - **Kelemahan:** jaminan probabilistik (ora paling parah); panunjuk tambahan saben node. ## Mulané iku penting Skip lists ngirim operasi tertib O(log n) kaya awak kode sing luwih sithik lan konkurensI lock-free gampang, mula sistem nyata kaya Redis milih.

Struktur

Panggolèkan

Kompleksitas

Trade-off lawan awak jurang berimbang

Mulané iku penting

Pitakon sing gegandhengan