A rank-aware skip list augments every forward pointer with a span: the number of bottom-level nodes that pointer crosses. Search still descends from higher express levels. During insertion, the predecessor path records how many entries were passed; the new node divides each affected span, while unaffected higher pointers gain one. Removal reverses those changes and can shrink empty top levels. Rank counts keys strictly less than a target; select follows spans until the requested zero-based position is reached. The sample rejects duplicate IDs, seeds a local random generator for reproducible heights, and caps tower height at twenty. The cap is a practical bound on stored levels, not a proof that a long list remains logarithmic after it is exceeded.
Span skip lists: rank and select without a full scan
Operational case
Insert alert IDs 61, 19, 83, 47, and 29. Exactly two IDs lie below 47, and position two selects 47. Removing 29 leaves [19,47,61,83]; rank and select must reflect the shorter bottom chain even when the removed node had no express-level pointers. A span on a pointer leading to an empty successor can still matter during an insertion at the end of the list. Updating only pointers that directly referenced a removed node leaves higher spans stale. The list is an ordered set of unique integer IDs and does not preserve insertion order for equal keys because equal keys are refused.
Working Python program
from random import Random
class AlertNode:
def __init__(self, alert_id, height):
self.alert_id = alert_id
self.forward = [None] * height
self.span = [0] * height
class RankedAlertIndex:
def __init__(self, seed=947, maximum_height=20):
self.head = AlertNode(None, maximum_height)
self.height = 1
self.length = 0
self.maximum_height = maximum_height
self.random = Random(seed)
def _height(self):
height = 1
while height < self.maximum_height and self.random.getrandbits(1):
height += 1
return height
def _predecessors(self, alert_id):
update = [None] * self.maximum_height
ranks = [0] * self.maximum_height
current = self.head
for level in range(self.height - 1, -1, -1):
ranks[level] = 0 if level == self.height - 1 else ranks[level + 1]
while current.forward[level] is not None and current.forward[level].alert_id < alert_id:
ranks[level] += current.span[level]
current = current.forward[level]
update[level] = current
return update, ranks
def add(self, alert_id):
update, ranks = self._predecessors(alert_id)
next_node = update[0].forward[0]
if next_node is not None and next_node.alert_id == alert_id:
return False
node_height = self._height()
if node_height > self.height:
for level in range(self.height, node_height):
ranks[level] = 0
update[level] = self.head
self.head.span[level] = self.length
self.height = node_height
new_node = AlertNode(alert_id, node_height)
for level in range(node_height):
predecessor = update[level]
distance = ranks[0] - ranks[level]
new_node.forward[level] = predecessor.forward[level]
new_node.span[level] = predecessor.span[level] - distance
predecessor.forward[level] = new_node
predecessor.span[level] = distance + 1
for level in range(node_height, self.height):
update[level].span[level] += 1
self.length += 1
return True
def discard(self, alert_id):
update, _ = self._predecessors(alert_id)
target = update[0].forward[0]
if target is None or target.alert_id != alert_id:
return False
for level in range(self.height):
predecessor = update[level]
if predecessor.forward[level] is target:
predecessor.span[level] += target.span[level] - 1
predecessor.forward[level] = target.forward[level]
else:
predecessor.span[level] -= 1
while self.height > 1 and self.head.forward[self.height - 1] is None:
self.height -= 1
self.length -= 1
return True
def rank(self, alert_id):
"""Count IDs strictly below alert_id."""
_, ranks = self._predecessors(alert_id)
return ranks[0]
def select(self, position):
if position < 0 or position >= self.length:
raise IndexError(position)
traversed = 0
current = self.head
for level in range(self.height - 1, -1, -1):
while current.forward[level] is not None and traversed + current.span[level] <= position:
traversed += current.span[level]
current = current.forward[level]
return current.forward[0].alert_id
def ordered(self):
result = []
current = self.head.forward[0]
while current is not None:
result.append(current.alert_id)
current = current.forward[0]
return result
alert_index = RankedAlertIndex()
for alert_id in (61, 19, 83, 47, 29):
alert_index.add(alert_id)
print("rank below 47:", alert_index.rank(47))
print("position two:", alert_index.select(2))
alert_index.discard(29)
print("after removal:", alert_index.ordered())Output
rank below 47: 2
position two: 47
after removal: [19, 47, 61, 83]Time, space, and tradeoff
With independent coin-flip heights and a cap large enough for the list, search, insertion, removal, rank, and select have expected O(log N) work; each can take O(N) in an unlucky arrangement. Space is O(N) expected pointers and spans plus the fixed-height head. The example allocates O(H) temporary predecessor and rank arrays for maximum height H on each mutation. A basic skip list without spans can find keys quickly but must scan level zero to select an arbitrary rank. A Fenwick frequency array handles ranked integers over a fixed domain, whereas this index orders keys without allocating that whole domain.
Common Mistakes
- Do not update only a removed node's own pointer levels; higher spans also change.
- Do not mix zero-based select with one-based span distance.
- Do not accept duplicate keys without defining multiset rank semantics.
- Do not claim strict logarithmic bounds from randomized towers.
Connected lessons
- Trees and Heaps
- Data Structures
- Skip lists: randomized levels over an ordered bottom chain
- Fenwick frequency index: select the kth stored key
- AVL order statistics: maintain subtree sizes for rank and select
- Projects
- Quizzes
Compare this operation boundary with Ordered treaps: split, join, and select depot keys, Two-dimensional segment trees: correct sensors and sum rectangles, Range-majority indexes: verify a candidate before returning it, then complete the structure audit and decision quiz.