การแทรกและการลบจะดำเนินการเหมือนกับการดำเนินการรายการที่เชื่อมโยงกันยกเว้นองค์ประกอบ "สูง" ที่ต้องแทรกหรือลบออกจากรายการที่เชื่อมโยงกันมากกว่าหนึ่งรายการ O (n) การดำเนินงานซึ่งบังคับให้เราไปเยี่ยมชมทุกโหนดตามลำดับจากน้อยไปมาก (เช่นพิมพ์รายชื่อทั้งหมด) ให้โอกาสในการแสดง derandomization เบื้องหลังฉากของโครงสร้างระดับของรายการข้ามไปในทางที่ดีที่สุดนำรายการข้ามไปที่ O (log n) เวลาค้นหา (เลือกระดับของโหนดที่ จำกัด ของ i เป็น 1 บวกจำนวนครั้งที่เราสามารถแบ่ง i ถึง 2 ซ้ำ ๆ ก่อนที่มันจะกลายเป็นคี่นอกจากนี้ i = 0 สำหรับส่วนหัวอินฟินิตี้เชิงลบเนื่องจากเรามีกรณีพิเศษในการเลือก เป็นระดับที่เป็นไปได้สูงสุดสำหรับโหนดที่เป็นลบและ / หรือบวกอนันต์) อย่างไรก็ตามวิธีนี้ยังช่วยให้ใครรู้ได้ว่ามีโหนดทั้งหมดที่อยู่ในระดับสูงกว่า 1 โหนดอยู่หรือไม่และลบออกอีกทางเลือกหนึ่งคือเราสามารถสร้างโครงสร้างระดับให้เป็นแบบสุ่มโดยใช้วิธีดังต่อไปนี้
make all nodes level 1 j ← 1 while the number of nodes at level j > 1 do for each i'th node at level j do if i is odd if i is not the last node at level j randomly choose whether to promote it to level j+1 else do not promote end if else if i is even and node i-1 was not promoted promote it to level j+1 end if repeat j ← j + 1 repeat
ดัชนีการก้าวกระโดด
ตามที่อธิบายไว้ข้างต้น Skiplist จะสามารถแทรกและกำจัดค่าจากลำดับที่เรียงลำดับได้อย่างรวดเร็ว O (log n) มีเพียงช้า O (n) lookups ของค่าในตำแหน่งที่กำหนดในลำดับ (เช่นคืนค่า 500th) ; อย่างไรก็ตามด้วยการปรับเปลี่ยนเล็กน้อยของการค้นหาแบบสุ่มจะสามารถปรับปรุงการค้นหาให้เป็น O (log n)
function lookupByPositionIndex (i) node ← head i ← i + 1 # don't count the head as a step for level from top to bottom do while i ≥ node.width[level] do # if next step is not too far i ← i - node.width[level] # subtract the current width node ← node.next[level] # traverse forward at the current level repeat repeat return node.value end function
อ้างอิง
Pugh, W. (1990). "Skip lists: A probabilistic alternative to balanced trees" (PDF). Communications of the ACM. 33 (6): 668. doi:10.1145/78973.78977.
Munro, J. Ian; Papadakis, Thomas; Sedgewick, Robert (1992). "Deterministic skip lists" (PDF). Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92). Orlando, Florida, USA: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. pp. 367–375. doi:10.1145/139404.139478.
ธันวาคม 07, 2021
รายการข, าม, อสงส, ยว, าบทความน, อาจละเม, ดล, ขส, ทธ, แต, ระบ, ไม, ได, ดเจนเพราะขาดแหล, งท, มา, หร, ออ, างถ, งส, งพ, มพ, งตรวจสอบไม, ได, หากแสดงได, าบทความน, ละเม, ดล, ขส, ทธ, ให, แทนป, ายน, วย, ละเม, ดล, ขส, ทธ, หากค, ณม, นใจว, าบทความน, ไม, ได, ละเม, ดล, ขส,. mikhxsngsywabthkhwamnixaclaemidlikhsiththi aetrabuimidchdecnephraakhadaehlngthima hruxxangthungsingphimphthiyngtrwcsxbimid hakaesdngidwabthkhwamnilaemidlikhsiththi ihaethnpaynidwy laemidlikhsiththi hakkhunmnicwabthkhwamniimidlaemidlikhsiththi ihaesdnghlkthaninhnaxphipray oprdxyanapaynixxkkxnmikhxsrupinwithyakarkhxmphiwetxr karkawkraoddepnokhrngsrangkhxmulthichwyihsamarthkhnhaidxyangrwderw phayinladbkhxngxngkhprakxb karkhnhaxyangrwderwthaidodykarrksaladbchnthiechuxmoyngknkhxng subsequences odythiladbchntxenuxngcakhamipyngxngkhprakxbthinxykwakxnhnani karkhnhacaerimtninladbchnthielkthisudcnkwacaphbxngkhprakxbsxngxyangtxenuxnghnungswnmikhnadelkaelaihykwahruxethakbxngkhprakxbthikhnha phanladbchnthiechuxmoyngxngkhprakxbthngsxngniechuxmoyngkbxngkhprakxbkhxngladbchnthiebabangthisudthdipsungkarkhnhacadaenintxipcnkwaeracakhnhaladbthnghmd xngkhprakxbthithukkhamipxaccaidrbkarkhdeluxkihepniptamkhwamepnipid 1 hrux deterministically 2 kbxditepneruxngthrrmdamakkhunlksna aekikhraylaexiydkardaeninkar aekikh xngkhprakxbthiichsahrbraykarkhamcamimakkwahnungtwchienuxngcaksamarthmiswnrwminmakkwahnungraykarkaraethrkaelakarlbcadaeninkarehmuxnkbkardaeninkarraykarthiechuxmoyngknykewnxngkhprakxb sung thitxngaethrkhruxlbxxkcakraykarthiechuxmoyngknmakkwahnungraykar O n kardaeninngansungbngkhbiheraipeyiymchmthukohndtamladbcaknxyipmak echnphimphraychuxthnghmd ihoxkasinkaraesdng derandomization ebuxnghlngchakkhxngokhrngsrangradbkhxngraykarkhamipinthangthidithisudnaraykarkhamipthi O log n ewlakhnha eluxkradbkhxngohndthi cakd khxng i epn 1 bwkcanwnkhrngthierasamarthaebng i thung 2 sa kxnthimncaklayepnkhinxkcakni i 0 sahrbswnhwxinfinitiechinglbenuxngcakeramikrniphiessinkareluxk epnradbthiepnipidsungsudsahrbohndthiepnlbaela hruxbwkxnnt xyangirktamwithiniyngchwyihikhrruidwamiohndthnghmdthixyuinradbsungkwa 1 ohndxyuhruximaelalbxxkxikthangeluxkhnungkhuxerasamarthsrangokhrngsrangradbihepnaebbsumodyichwithidngtxipni make all nodes level 1 j 1 while the number of nodes at level j gt 1 do for each i th node at level j do if i is odd if i is not the last node at level j randomly choose whether to promote it to level j 1 else do not promote end if else if i is even and node i 1 was not promoted promote it to level j 1 end if repeat j j 1 repeat dchnikarkawkraoddtamthixthibayiwkhangtn Skiplist casamarthaethrkaelakacdkhacakladbthieriyngladbidxyangrwderw O log n miephiyngcha O n lookups khxngkhaintaaehnngthikahndinladb echnkhunkha 500th xyangirktamdwykarprbepliynelknxykhxngkarkhnhaaebbsumcasamarthprbprungkarkhnhaihepn O log n sahrbthuklingkihekbkhwamkwangkhxnglingkdwy khwamkwangthukkahndepncanwnlingkkhxngchnlangthikalngsarwcodylingk chxngthangdwn aetlachnsungkwa twxyangechnnikhuxkhwamkwangkhxnglingkintwxyangthidanbnkhxnghna 1 10 o gt o gt o Top level 1 3 2 5 o gt o gt o gt o gt o Level 3 1 2 1 2 3 2 o gt o gt o gt o gt o gt o gt o Level 2 1 1 1 1 1 1 1 1 1 1 1 o gt o gt o gt o gt o gt o gt o gt o gt o gt o gt o gt o Bottom level Head 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th NIL Node Node Node Node Node Node Node Node Node Nodesngektwakhwamkwangkhxnglingkradbthisungkhunkhuxphlrwmkhxnglingkkhxmophenntdanlang echnkhwamkwang 10 cakhrxbkhlumlingkthimikhwamkwang 3 2 aela 5 danlang dngnnphlrwmkhxngkhwamkwangthnghmdcaehmuxnkninthukradb 10 1 1 3 2 5 1 2 1 2 5 emuxtxngkarcdthadchniraykarkhamaelakhnhakha i th ihkhamraykarkhamkhnathinbkhwamkwangkhxngaetlalingk ldradblngemuxkhwamkwangthicaekidkhuncaihyekinip twxyangechnhaktxngkarhaohndintaaehnngthi 5 ohnd 5 ihkhamkarechuxmoyngkhxngkhwamkwang 1 thiradbbnsud txnnicaepntxngichsikhntxnephimetim aetkhwamkwangtxipinradbnikhuxsibsungihyekinipdngnncungldlnghnungradb khamiphnunglingkkhxngkhwamkwang 3 enuxngcakxikkawhnungkhxngkhwamkwang 2 caiklekinipeluxnlngipthiradblang txnnisarwckarechuxmoyngkhnsudthaykhxngkhwamkwang 1 ipthungepahmaythieriykichnganthnghmd 5 1 3 1 function lookupByPositionIndex i node head i i 1 don t count the head as a step for level from top to bottom do while i node width level do if next step is not too far i i node width level subtract the current width node node next level traverse forward at the current level repeat repeat return node value end functionxangxing aekikh Pugh W 1990 Skip lists A probabilistic alternative to balanced trees PDF Communications of the ACM 33 6 668 doi 10 1145 78973 78977 Munro J Ian Papadakis Thomas Sedgewick Robert 1992 Deterministic skip lists PDF Proceedings of the third annual ACM SIAM symposium on Discrete algorithms SODA 92 Orlando Florida USA Society for Industrial and Applied Mathematics Philadelphia PA USA pp 367 375 doi 10 1145 139404 139478 ekhathungcak https th wikipedia org w index php title raykarkham amp oldid 9087196, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
