Java实现跳跃列表中的删除方法

Question

我的跳过列表的删除方法正在无限循环!我按照这个网站http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html的伪代码进行操作。除了删除之外，其他方法似乎工作正常。这是我的代码:

public void delete(String k) {
    SkipListEntry p = findEntry(k);

    if (p.key != k) {
        return; // Not found, don't remove
    }

    while (p != null) {
        //need to delete the entry from each list using the "up" or "down" links
        p.left.right = p.right;
        p.right.left = p.left;  
    }
}

这是我的整个代码http://pastebin.com/StJRzixN
谢谢

Answer 1

您缺少删除中的一个步骤。

在递归调用之前，需要将p赋值给p.up。

否则，您将坐在最低层的 p 上，并不断调整邻居的右和左指针。