java - Skiplist - 尝试实现 get() 和 set() 方法

Question

所以我试图实现一个 FastDefaultList 类，它基本上是一个跳跃列表，表示索引为 0,1,2,3,…,∞ 的无限列表。开始时，此列表中的每个值都被分配默认值 null。否则，这个类的行为就像一个列表；它具有 add(i,x)、remove(i)、set(i,x) 和 get(i)，其行为与列表中的相同方法相同。每个操作都应在 O(log n) 时间内运行。我的很多跳过列表代码都来自:

https://opendatastructures.org/odsjava/4_2_SkiplistSSet_Efficient_.html

我认为我已经完成了大部分工作，但我正在尝试修复我的 get() 和 set() 方法。每当我尝试编译该程序时，我都会收到错误:

错误:找不到适合 add(int,FastDefaultList.Node,int) 的方法 添加(i，节点，0)；

我不知道为什么。任何帮助将不胜感激。

package comp;
import java.lang.reflect.Array;
import java.lang.IllegalStateException;
import java.util.AbstractList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Random;


public class FastDefaultList<T> extends AbstractList<T> {
    class Node {
        T x;
        Node[] next;
        int[] length;
        @SuppressWarnings("unchecked")
        public Node(T ix, int h) {
            x = ix;
            next = (Node[])Array.newInstance(Node.class, h+1);
            length = new int[h+1];
        }
        public int height() {
            return next.length - 1;
        }
    }

    /**
     * This node sits on the left side of the skiplist
     */
    protected Node sentinel;

    /**
     * The maximum height of any element
     */
    int h;

    /**
     * The number of elements stored in the skiplist
     */
    int n;   // Hint: You don't need this anymore!

    /**
     * A source of random numbers
     */
    Random rand;


    public FastDefaultList() {
        n = 0;
        sentinel = new Node(null, 32);
        h = 0;
        rand = new Random(0);
    }


    /**
     * Represents a node/index Pair
     */
    protected class Pair {
        Node u;
        int j;

        Pair(Node u, int j) {
            this.u = u;
            this.j = j;
        }
    }

    protected Pair findPred(int i) {
        Node u = sentinel;
        int r = h;
        int j = -1;   // index of the current node in list 0
        while (r >= 0) {
            while (u.next[r] != null && j + u.length[r] < i) {
                j += u.length[r];
                u = u.next[r];
            }
            r--;
        }
        return new Pair(u, j);
    }

    public T get(int i) {

        if (i < 0 || i > size()-1) throw new IndexOutOfBoundsException();
        Pair n = findPred(i);
        if(n.u.next[0] != null && n.j + n.u.length[0] == i){ return n.u.next[0].x; }
        return null;        
    }

    public T set(int i, T x) {

        if (i < 0 || i > size()-1) throw new IndexOutOfBoundsException();
        Pair n = findPred(i);
        if (n.u.next[0] != null && n.j + n.u.length[0] == i) {
            Node u = n.u.next[0];
            T y = u.x;
            u.x = x;
            return y;
        }
        else{
            Node node = new Node(x, pickHeight());
            if(node.height() > h){ h = node.height(); }
            add(i, node, 0);
        }
        return null;
    }

    /**
     * Insert a new node into the skiplist
     * @return the node u that precedes v in the skiplist
     */
    protected Node add(int i, Node w) {
        Node u = sentinel;
        int k = w.height();
        int r = h;
        int j = -1; // index of u
        while (r >= 0) {
            while (u.next[r] != null && j+u.length[r] < i) {
                j += u.length[r];
                u = u.next[r];
            }
            u.length[r]++; // accounts for new node in list 0
            if (r <= k) {
                w.next[r] = u.next[r];
                u.next[r] = w;
                w.length[r] = u.length[r] - (i - j);
                u.length[r] = i - j;
            }
            r--;
        }
        n++;
        return u;
    }

    /**
     * Simulate repeatedly tossing a coin until it comes up tails.
     * Note, this code will never generate a height greater than 32
     * @return the number of coin tosses - 1
     */
    protected int pickHeight() {
        int z = rand.nextInt();
        int k = 0;
        int m = 1;
        while ((z & m) != 0) {
            k++;
            m <<= 1;
        }
        return k;
    }

    public void add(int i, T x) {
        if (i < 0 || i > size()-1) throw new IndexOutOfBoundsException();
        Node w = new Node(x, pickHeight());
        if (w.height() > h)
            h = w.height();
        add(i, w);
    }

    public T remove(int i) {
        if (i < 0 || i > size()-1) throw new IndexOutOfBoundsException();
        T x = null;
        Node u = sentinel;
        int r = h;
        int j = -1; // index of node u
        while (r >= 0) {
            while (u.next[r] != null && j+u.length[r] < i) {
                j += u.length[r];
                u = u.next[r];
            }
            u.length[r]--;  // for the node we are removing
            if (j + u.length[r] + 1 == i && u.next[r] != null) {
                x = u.next[r].x;
                u.length[r] += u.next[r].length[r];
                u.next[r] = u.next[r].next[r];
                if (u == sentinel && u.next[r] == null)
                    h--;
            }
            r--;
        }
        n--;
        return x;
    }


    public int size() {
        return Integer.MAX_VALUE;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
            int i = -1;
            Node u = sentinel;
            while (u.next[0] != null) {
                i += u.length[0];
                u = u.next[0];
                sb.append(" " + i + "=>" + u.x);
            }
            return sb.toString();
    }

    public static void main(String[] args) {

    }
}

Answer 1

您的添加函数接受 2 个参数

protected Node add(int i, Node w)

但是你用 3 个参数来调用它 -

这里:

 if(node.height() > h){ h = node.height(); }
        add(i, node, 0);