Cad is ea skip list agus conas a bhíonn O(log n) cuardaigh aici?

Question

Accepted Answer

Is **skip list** a bhíonn ann ná liosta nasc ordúil a bhíonn fealadh ag níos mó leibhéal **"bóithre gasta"**. Bíonn na leibhéal níos airde ag foluain thar go leor nóid, agus mar sin déanann an cuardach dul síos agus gluaiseacht ar dheis, agus bíonn am ionchasach de **O(log n)** air — rogha thairbhiúil dheascruthaitheach atá níos simplí ná crann cothrom. ## Struchtúr ```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) ``` Cuirtear gach nód chun leibhéal níos airde le dóchúlacht `p` (go minic 0.5), agus ar an meán bíonn leath líon na nóid ag gach leibhéal atá thíos. ## Cuardach ```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 ``` ## Casta | Oibríocht | Ionchasach | Spás | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Malartú in aghaidh crann cothrom - **Láidreachtaí:** i bhfad níos simplí a chur i bhfeidhm ná red-black/AVL; gan rothlú; leaganacha comhthreomharacha éasca (úsáidtear i dtacair rainn Redis, `ConcurrentSkipListMap` Java). - **Laigí:** bar bharúlacha (ní dhéanfar píc-chás); pointeoir breise in aghaidh nód. ## Cad a Dhéanann Sé an Spéis Agamh Soláthraíonn skip lists oibríochtaí ordúil cosúil le crann in O(log n) le i bhfad níos lú cód agus comhthreomharachas gan chnaipe éasca, arb é sin an fáth go roghnaíonn córas i ndáiríribh cosúil le Redis iad. Tá siad ina samplaí cumasach ar **randúchán** a úsáid chun loighic bhreisithe chinnte atá casta a ionadú.