\"previous question\": Suggest a modification of the SkipList structure, such th

Question

"previous question":

Suggest a modification of the SkipList structure, such that in addition to the operations insert(x), find(x) and delete(x), you could also answer the operation LesserThan(x) specifying the sum of all the keys in the SkipList are strictly smaller than x. The expected time for each operation should be O(log n).

Hint: Store at each node v of the SL another field, called size[v], containing the number of keys in the SL between v and the next node at the same level as v. Note that maintaining the values of these fields might imply extra work while performing other operations.

In addition to the operations mentioned in the previous question, now support also range(x1, x2) which returns the sum of all keys which are x1 and x2. The expected time for every operation is O(log n).

Explanation / Answer

Assume u has children u1, u2, ...

Count[u] = 1 + Count[u1] + Count[u2] + ...

typedef struct snode {
int key;
int value;
struct snode **forward;
} snode;

typedef struct skiplist {
int level;
int size;
int less_than;
struct snode *header;
} skiplist;

skiplist *skiplist_init(skiplist *list) {
int i;
snode *header = (snode *) malloc(sizeof(struct snode));
list->header = header;
header->key = INT_MAX;
header->forward = (snode **) malloc(
sizeof(snode*) * (SKIPLIST_MAX_LEVEL + 1));
for (i = 0; i <= SKIPLIST_MAX_LEVEL; i++) {
header->forward[i] = list->header;
}

list->level = 1;
list->size = 0;
list->less_than = 0

return list;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.