Изменения

Список с пропусками

41 байт добавлено, 04:34, 16 июня 2014

м

Псевдокод отформатирован

int lvl = (int)(log(frand())/log(1.-P))

if lvl < MAX_LEVEL

return lvl

return MAX_LEVEL

SkipNode x = header

for i = level to 0

while x.forward[i] != NULL and x.forward[i].value < key x = x.forward[i] x = x.forward[0]

return x != NULL && x.value == key

for i = level to 0

while x.forward[i] != NULL and x.forward[i].value < value x = x.forward[i] update[i] = x

x = x.forward[0]

if x == NULL or x.value != value

int lvl = random_level()

if lvl > level

for i = level + 1 to lvl update[i] = header level = lvl

x = new SkipNode(lvl, value)

for i = 0 to lvl x.forward[i] = update[i].forward[i] update[i].forward[i] = x

SkipNode x = header

SkipNode update

update.assign(MAX_LEVEL + 1, 0)

for i = level to 0

while x.forward[i] != NULL and x.forward[i].value < value x = x.forward[i] update[i] = x x = x.forward[0]

if x.value == value

for i = 0 to level

if update[i].forward[i] != x break update[i].forward[i] = x.forward[i];

delete x

while level > 0 or header.forward[level] == NULL

level--

47

правок