Clarification on the data structure SkipList

[ScobY9]

Hi,

I looked through the codes provided, and got confused about the
following:

Does SkipTower represent the vertical tower shown on the lecture
slide?
What does the tower field in SkipTower represent?
How would the following skip list be represented by this
implementation?

-inf, inf
-inf, 65, inf
-inf, 37, 65, 80, inf

Thanks.

[cs240]

Post by ScobY9
Does SkipTower represent the vertical tower shown on the lecture
slide?

Yes, a skip tower is a vertical tower.

Post by ScobY9
What does the tower field in SkipTower represent?

tower[i] is a pointer to the following SkipTower in L_i.

Post by ScobY9
How would the following skip list be represented by this
implementation?
-inf, inf
-inf, 65, inf
-inf, 37, 65, 80, inf

I suggest using the print method and gdb to examine the structure.

listHead
|
V

L2 -inf -> inf
L1 -inf -> 65 -> inf
L0 -inf -> 37 -> 65 -> 80 -> inf

[Daniel S. Roche]

Post by ScobY9
What does the tower field in SkipTower represent?
How would the following skip list be represented by this
implementation?
-inf, inf
-inf, 65, inf
-inf, 37, 65, 80, inf

Just to elaborate a bit further on Patrick's response, in this example
there will be 5 skip towers which I will call t1..t5, with the following
keys:
t1.key = -inf
t2.key = 37
t3.key = 65
t4.key = 80
t5.key = inf

(Note: inf and -inf are accessed in C++ by writing HUGE_VAL and
-HUGE_VAL, respectively.)

The towers will be vectors of pointers to the adjacent SkipTower in each
list. The size of each tower will be exactly one more than the height of
that KVP in the skip list. So the towers are:

t1.tower = [&t2, &t3, &t5]
t2.tower = [&t3]
t3.tower = [&t4, &t5]
t4.tower = [&t5]
t5.tower = [NULL, NULL, NULL]

I hope this clears up any confusion.

-Dan Roche
CS 240 Instructor, Section 003