Как мы можем обновить длину каждого указателя при вставке списка пропуска Sortedset? ⇐ JAVA

[Anonymous]

Я реализую вставку для Sortset SkipList. Все было в порядке, но теперь мне нужно заставить get(index) работать в O(logn). Это означает, что мне нужно объединить список пропуска Sortedset и список пропуска. Итак, как я могу обновить длину указателей, сохраняя при этом порядок элементов в наборе?
public boolean add(T x) {

Node u = sentinel;
int r = h;
int comp = 0;
int j = -1; // Track index position as we traverse
Node 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 = stack.next;
stack.next = w;

// Calculate the lengths for `w` and `stack`

}

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


Подробнее здесь: https://stackoverflow.com/questions/791 ... -insertion