Skip lists: a probabilistic alternative to balanced trees Export

@article{citeulike:1352856, abstract = {Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.}, address = {New York, NY, USA}, author = {Pugh, William}, citeulike-article-id = {1352856}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=78973.78977}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/78973.78977}, doi = {10.1145/78973.78977}, issn = {0001-0782}, journal = {Commun. ACM}, keywords = {1990, datastructures}, month = {June}, number = {6}, pages = {668--676}, posted-at = {2009-06-03 12:57:32}, priority = {2}, publisher = {ACM}, title = {Skip lists: a probabilistic alternative to balanced trees}, url = {http://dx.doi.org/10.1145/78973.78977}, volume = {33}, year = {1990} }

TY - JOUR ID - citeulike:1352856 L3 - citeulike-article-id:1352856 N2 - Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees. IS - 6 JF - Commun. ACM SN - 0001-0782 AD - New York, NY, USA EP - 676 TI - Skip lists: a probabilistic alternative to balanced trees PB - ACM VL - 33 SP - 668 KW - 1990 KW - datastructures AU - Pugh, William PY - 1990/06// UR - http://dx.doi.org/10.1145/78973.78977 ER -