Skip List (Rust)
Topics: skip list, probabilistic ordered map, range scan
Problem
Implement a skip list — a probabilistic ordered map with O(log n) expected insert/get and
ordered range scans. It's the structure behind Redis sorted sets and LevelDB's memtable, and
a popular alternative to balanced trees because there's no rotation/rebalancing.
pub struct SkipList { /* … */ }
impl SkipList {
pub fn new() -> Self;
pub fn get(&self, key: i32) -> Option<i32>;
pub fn insert(&mut self, key: i32, val: i32);
pub fn range(&self, lo: i32, hi: i32) -> Vec<(i32, i32)>; // ascending, lo <= key <= hi
}
Each node gets a random tower height; the higher levels are "express lanes" that skip many nodes,
so search drops down level by level.
insert adds or updates a key. Record, per level, the last node before the key (the update
path), give the new node a random height (rand_level, provided), splice it in at each level, and
raise self.level if its tower is the tallest so far.get searches from the top level down.range finds the first node >= lo, then walks level 0 until > hi.
Key concepts
- Index arena: nodes live in a
Vec<Node> with forward links as Option<usize> — no raw
pointers or Rc<RefCell> (alloc is provided).
- Towers + express lanes: ~½ of nodes reach level 2, ~¼ level 3, … giving logarithmic search
with no rebalancing.
- Deterministic by design here: a fixed-seed xorshift (
rand_level) drives the coin flips so
tests are stable; correctness never depends on the randomness.
The arena, new, alloc, and rand_level are provided; you implement get, insert, range.
Grading
Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using
rustc --test. Only solution.rs is yours to edit.
Sign in to submit your solution.