90
правок
Изменения
Нет описания правки
# Найти удаляемый элемент
# Удалить его со всех уровней
==Псевдокод==
<code>
const float P = 0.5
int random_level()
int lvl = (int)(log(frand())/log(1.-P))
return lvl < MAX_LEVEL ? lvl : MAX_LEVEL
boolean Find (int key)
SkipNode x = header
for (int i = level; i >= 0; i--)
while (x.forward[i] != NULL && x.forward[i].value < key)
x = x.forward[i]
x = x.forward[0]
return x != NULL && x.value == key
void Insert(int value)
SkipNode x = header
SkipNode update
update.assign(MAX_LEVEL + 1, 0)
for (int i = level; i >= 0; i--)
while (x.forward[i] != NULL && x.forward[i].value < value)
x = x.forward[i]
update[i] = x
x = x.forward[0]
if (x == NULL || x.value != value)
int lvl = random_level()
if (lvl > level)
for (int i = level + 1; i <= lvl; i++)
update[i] = header
level = lvl
x = new SkipNode(lvl, value)
for (int i = 0; i <= lvl; i++)
x.forward[i] = update[i].forward[i]
update[i].forward[i] = x
void Erase(int value)
SkipNode x = header
SkipNode update
update.assign(MAX_LEVEL + 1, 0)
for (int i = level; i >= 0; i--)
while (x.forward[i] != NULL && 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 <= level; i++)
if (update[i].forward[i] != x)
break
update[i].forward[i] = x.forward[i];
delete x
while (level > 0 && header.forward[level] == NULL)
level--
</code>
==Ссылки==
