Çfarë është një skip list dhe si arrin O(log n) kërkim?

Question

Accepted Answer

A **skip list** është një listë e lidhur e renditur e zmadhuar me disa **"express lane"** nivele. Nivelet më të larta kapërcejnë shumë nyje, kështu që kërkimi zbret dhe lëviz djathtas, duke arritur **O(log n)** kohë të pritur — si një alternativë probabilistike, më e thjeshtë ndaj një peme të balancuar. ## Struktura ```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) ``` Seccila nyje ngrohet në nivelet më të larta me probabilitet `p` (shpesh 0.5), kështu në mesatare secili nivel ka gjysma më pak nyjesh se ai poshtë tij. ## Kërkimi ```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 ``` ## Kompleksiteti | Operacioni | I pritur | Hapësira | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Kompromise ndaj pemëve të balancuara - **Përparësit:** shumë më të thjeshtë për implementim sesa red-black/AVL; pa rotacione; versione të lehtë konkurente (të përdorura në Redis sorted sets, Java `ConcurrentSkipListMap`). - **Dobësit:** garancit probabilistike (jo në rastin më të keq); tregues shtesë për nyje. ## Pse është e rëndësishme Skip lists ofrojnë operacione të ngjashme me pemën, O(log n) të renditur me shumë më pak kod dhe konkurrencë të lehtë pa kyçe, kështu që sistemet reale si Redis i zgjedhin ato. Ato janë një shembull i shkëlqyer i përdorimit të **rastësisë** për të zëvendësuar logjikën komplekse deterministe të balancimit.