Violation of the deterministic scrolling of the skip list

Question

Suppose I have been given a skip list, with order 3.

           HEAD
level 3     |--------------------------------------------> X
            |                      |---|
level 2     | -------------------> |   | ----------------> X
            |    |---|    |---|    |---|    |---|
level 1     | -> |   | -> |   | -> |   | -> |   | -------> X
            |    |---|    |---|    |---|    |---|
            |    | 20|    |100|    |150|    |200|
            |    |---|    |---|    |---|    |---|


minlimit = ceil(order/2) - 1 = 1

maxlimit = order - 1 = 2

So essentially this is a 1-2 skip-list.

If I want to paste 50using the insertion algorithm from top to bottom, it will raise the node level 100before moving on to the gap between Headand 150and paste 50to the right to 100. Now the violation will occur, since there are no nodes between 100and 150, while in this space there should be at least a node of height h-1.

What am I doing wrong?

Answer 1

50 , node 100, Head 150 50 100

?

, 1-2 ( ), (PDF) :

[...], ... ,... , 1-2-3 3 1, , . , .

, 1 . , , , 3 , ; . , node 1.

3 2 . - node 150 - . 2 [HEAD, 150].

?

Answer 2

50 , node 100, Head 150 50 100.

node 100. node 20. , , maxlimit , ceil((maxlimit/2))th node .

, node 20 2, node 20 1 node . , Munro et al. .

, n 0- a (n + 1) st node 1 , , h ( h > 1) , 1, 2 h - 1.