90
правок
Изменения
Нет описания правки
int random_level()
int lvl = (int)(log(frand())/log(1.-P))
boolean Find (int key)
x = x.forward[i]
x = x.forward[0]
update.assign(MAX_LEVEL + 1, 0)
for (int i = level; i >= to 0; i--) while (x.forward[i] != NULL && and x.forward[i].value < value)
x = x.forward[i]
update[i] = x
int lvl = random_level()
if (lvl > level) for (int i = level + 1; i <= to lvl; i++)
update[i] = header
level = lvl
x = new SkipNode(lvl, value)
for (int i = 0; i <= to lvl; i++)
x.forward[i] = update[i].forward[i]
update[i].forward[i] = x
SkipNode update
update.assign(MAX_LEVEL + 1, 0)
for (int i = level; i >= to 0; i--) 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 (int i = 0; i <= to level; i++) 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--
