SKIP LISTS - A PROBABILISTIC ALTERNATIVE TO BALANCED TREES

被引：545

作者：

PUGH, W ^{[1
]}

机构：

[1] UNIV MARYLAND,INST ADV COMP STUDIES,COLLEGE PK,MD 20742

来源：

COMMUNICATIONS OF THE ACM | 1990年 / 33卷 / 06期

关键词：

data structures; searching; trees;

D O I：

10.1145/78973.78977

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. © 1990, ACM. All rights reserved.

引用

页码：668 / 676

页数：9

共 12 条

[1] Aho A., 1983, DATA STRUCTURES ALGO
[2] ARAGON CR, 1989, 30TH P ANN IEEE S F, P540
[3] BENTLEY J, 1986, MITLCS297 TECH REP
[4] Knuth D.E., 1997, ART COMPUTER PROGRAM, V3
[5] PAPADAKIS T, 1990, JUL SCAND WORKSH ALG
[6] PUGH W, INFORM PROCESS LETT, V34, P251
[7] PUGH W, 1989, TRCS2222 U MAR DEP C
[8] PUGH W, 1989, CSTR22861 U MAR DEP
[9] PUGH W, 1989, 16TH P C PRINC PROGR
[10] SELF-ADJUSTING BINARY SEARCH-TREES
SLEATOR, DD
TARJAN, RE
[J]. JOURNAL OF THE ACM, 1985, 32 (03) : 652 - 686

← 1 2 →