如何更新Sortedset Skip List插入中每个指针的长度？

Question

我正在实现 Sortset SkipList 的插入。没关系，但现在我需要让我的 get(index) 在 O(logn) 中运行。这意味着我必须结合 Sortedset Skiplist 和 Skiplist list。那么如何更新指针的长度，同时保持集合中元素的顺序？

public boolean add(T x) {

        Node<T> u = sentinel;
        int r = h;
        int comp = 0;
        int j = -1; // Track index position as we traverse
        Node<T> w = new Node<>(x, pickHeight());

        // Traverse the levels from top down to find the correct position for `x`
        while (r >= 0) {
            while (u.next[r] != null && (comp = c.compare(u.next[r].x, x)) < 0) {

                u = u.next[r];
            }
            // Increment length on level `r` to account for the new node
            ;
            if (u.next[r] != null && comp == 0) return false; // Duplicate, exit early

            stack[r--] = u; // Store the node `u` in the stack for each level
        }

        // Update height if the new node `w` requires it
        while (h < w.height()) {
            stack[++h] = sentinel;
            sentinel.length[h] = n + 1;
        }

        j++; // `j` now represents the exact insertion index for `w`

        // Insert `w` and update lengths at each level
        for (int i = 0; i < w.next.length; i++) {

            w.next[i] = stack[i].next[i];
            stack[i].next[i] = w;

            // Calculate the lengths for `w` and `stack[i]`

        }

        n++; // Increment node count
        return true;
    }

Answer 1

在跳表的每个节点中，还可以存储本节点与下一个同级节点之间的元素个数（包括下一个节点，但不包括当前节点）。

添加元素时，按照通常的方式通过跳跃列表插入查找新值的所有前导元素。在搜索前辈时，跟踪每个级别所涵盖的元素数量。对于新插入的值所在的每个级别，将从前一个节点到新节点的元素数量更新为从底部级别到当前级别覆盖的所有元素的总和加一。新节点采用先前在前任节点和下一个节点之间的剩余元素的计数。对于不在不包含新值的级别上的前辈，只需将其元素数量增加到下一个节点即可。

删除节点时，对于每个前驱节点，将比要删除的节点与其下一个节点之间覆盖的元素个数少1个添加到前驱节点（如果要删除的节点在本层不存在，则该计数为零） ).

要实现按排名/索引查找，请使用类似的过程来搜索元素，但不是比较键，而是通过向前移动时对级别上相邻节点之间的元素计数求和来维护当前传递的元素计数。