Suggest a modification of the SkipList structure, such that in addition to the o

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.

Explanation / Answer

Statement sum of all is a little confusing it can either mean sum of values less than that specific value x or the total number of values less than x.I will try to answer for the number of values.

In each node, we maintain a Count.

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 S
• Subjects

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