Skip Lists

import random

class SkipNode:
    """A single node in the skip list. Contains a value and an array
    of forward pointers — one per level the node participates in."""
    def __init__(self, val, level):
        self.val = val
        # forward[i] points to the next node at level i
        self.forward = [None] * (level + 1)

class SkipList:
    """Skip list with search, insert, delete, and range query.
    
    MAX_LEVEL caps the height to O(log n). P controls the probability
    of a node being promoted to a higher level. p=0.5 gives the most
    balanced structure; p=0.25 (Redis) saves memory.
    """
    MAX_LEVEL = 16   # Supports up to 2^16 = 65536 elements efficiently
    P = 0.5          # Probability of promoting to next level

    def __init__(self):
        # Header is a sentinel node — it exists at all levels
        # and has value -infinity (never matches a search)
        self.header = SkipNode(-1, self.MAX_LEVEL)
        self.level = 0  # Current highest level in use
        self.size = 0

    def _random_level(self):
        """Generate a random level using geometric distribution.
        Each level has P probability of promotion.
        Expected level = 1/(1-P). With P=0.5, average level is ~1."""
        lvl = 0
        while random.random() < self.P and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl

    def search(self, target):
        """Search for a value. Returns True/False. O(log n) expected."""
        current = self.header
        # Start from highest level, work down
        for i in range(self.level, -1, -1):
            # Move right while the next node's value is less than target
            while current.forward[i] and current.forward[i].val < target:
                current = current.forward[i]
        # Now at level 0, one step away from target position
        current = current.forward[0]
        return current is not None and current.val == target

    def insert(self, val):
        """Insert a value into the skip list. O(log n) expected."""
        # update[i] = the last node at level i before the insertion point
        update = [None] * (self.MAX_LEVEL + 1)
        current = self.header

        # Search for insert position, recording predecessors at each level
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].val < val:
                current = current.forward[i]
            update[i] = current

        # Generate random height for the new node
        new_level = self._random_level()

        # If new node is taller than current max, extend update array
        if new_level > self.level:
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.header  # Header is predecessor at new levels
            self.level = new_level

        new_node = SkipNode(val, new_level)

        # Splice the new node into each level it participates in
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

        self.size += 1

    def delete(self, val):
        """Delete a value from the skip list. Returns True if found. O(log n)."""
        update = [None] * (self.MAX_LEVEL + 1)
        current = self.header

        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].val < val:
                current = current.forward[i]
            update[i] = current

        target = current.forward[0]
        if target is None or target.val != val:
            return False  # Value not found

        # Remove target from each level it appears in
        for i in range(self.level + 1):
            if update[i].forward[i] != target:
                break  # target doesn't exist at this level or above
            update[i].forward[i] = target.forward[i]

        # Shrink max level if top levels are now empty
        while self.level > 0 and self.header.forward[self.level] is None:
            self.level -= 1

        self.size -= 1
        return True

    def range_query(self, lo, hi):
        """Return all values in [lo, hi] inclusive. O(log n + k)."""
        results = []
        current = self.header

        # Search for the first node >= lo
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].val < lo:
                current = current.forward[i]

        # Walk level 0 and collect values until we pass hi
        current = current.forward[0]
        while current and current.val <= hi:
            results.append(current.val)
            current = current.forward[0]

        return results

    def to_list(self):
        """Return all values in sorted order. O(n)."""
        result = []
        current = self.header.forward[0]
        while current:
            result.append(current.val)
            current = current.forward[0]
        return result


# Usage
sl = SkipList()
for val in [3, 6, 7, 9, 12, 19, 17, 26, 21, 25]:
    sl.insert(val)

print(sl.search(19))          # True
print(sl.search(15))          # False
print(sl.range_query(10, 20)) # [12, 17, 19]
print(sl.to_list())           # [3, 6, 7, 9, 12, 17, 19, 21, 25, 26]

sl.delete(19)
print(sl.search(19))          # False
print(sl.range_query(10, 20)) # [12, 17]

class SkipList {
  constructor(maxLevel = 16, p = 0.5) {
    this.MAX_LEVEL = maxLevel;
    this.P = p;
    this.header = { val: -Infinity, forward: new Array(maxLevel + 1).fill(null) };
    this.level = 0;
    this.size = 0;
  }

  _randomLevel() {
    let lvl = 0;
    while (Math.random() < this.P && lvl < this.MAX_LEVEL) lvl++;
    return lvl;
  }

  search(target) {
    let cur = this.header;
    for (let i = this.level; i >= 0; i--) {
      while (cur.forward[i] && cur.forward[i].val < target) cur = cur.forward[i];
    }
    cur = cur.forward[0];
    return cur !== null && cur.val === target;
  }

  insert(val) {
    const update = new Array(this.MAX_LEVEL + 1).fill(null);
    let cur = this.header;
    for (let i = this.level; i >= 0; i--) {
      while (cur.forward[i] && cur.forward[i].val < val) cur = cur.forward[i];
      update[i] = cur;
    }
    const newLevel = this._randomLevel();
    if (newLevel > this.level) {
      for (let i = this.level + 1; i <= newLevel; i++) update[i] = this.header;
      this.level = newLevel;
    }
    const node = { val, forward: new Array(newLevel + 1).fill(null) };
    for (let i = 0; i <= newLevel; i++) {
      node.forward[i] = update[i].forward[i];
      update[i].forward[i] = node;
    }
    this.size++;
  }

  delete(val) {
    const update = new Array(this.MAX_LEVEL + 1).fill(null);
    let cur = this.header;
    for (let i = this.level; i >= 0; i--) {
      while (cur.forward[i] && cur.forward[i].val < val) cur = cur.forward[i];
      update[i] = cur;
    }
    const target = cur.forward[0];
    if (!target || target.val !== val) return false;
    for (let i = 0; i <= this.level; i++) {
      if (update[i].forward[i] !== target) break;
      update[i].forward[i] = target.forward[i];
    }
    while (this.level > 0 && !this.header.forward[this.level]) this.level--;
    this.size--;
    return true;
  }

  rangeQuery(lo, hi) {
    let cur = this.header;
    for (let i = this.level; i >= 0; i--) {
      while (cur.forward[i] && cur.forward[i].val < lo) cur = cur.forward[i];
    }
    const results = [];
    cur = cur.forward[0];
    while (cur && cur.val <= hi) {
      results.push(cur.val);
      cur = cur.forward[0];
    }
    return results;
  }
}

class SortedSet:
    """Simplified Redis ZSET using a skip list + hash map.
    
    The skip list provides O(log n) sorted operations (rank, range).
    The hash map provides O(1) score lookups by member name.
    Redis uses this exact dual-structure approach.
    """

    def __init__(self):
        self.skiplist = SkipList()  # Stores (score, member) tuples
        self.scores = {}           # member → score (for O(1) lookup)

    def zadd(self, member, score):
        """Add member with score. If member exists, update its score."""
        if member in self.scores:
            # Remove old entry first (score may have changed)
            old_score = self.scores[member]
            self.skiplist.delete(old_score)
        self.scores[member] = score
        self.skiplist.insert(score)

    def zscore(self, member):
        """Get the score of a member. O(1)."""
        return self.scores.get(member)

    def zrangebyscore(self, min_score, max_score):
        """Get all members with scores in [min, max]. O(log n + k)."""
        scores_in_range = self.skiplist.range_query(min_score, max_score)
        # In a real implementation, the skip list nodes would store both
        # score and member. Here we do a reverse lookup for simplicity.
        result = []
        score_to_members = {}
        for member, score in self.scores.items():
            score_to_members.setdefault(score, []).append(member)
        for score in scores_in_range:
            for member in score_to_members.get(score, []):
                result.append((member, score))
        return result

    def zrem(self, member):
        """Remove a member. O(log n)."""
        if member not in self.scores:
            return False
        score = self.scores.pop(member)
        self.skiplist.delete(score)
        return True

    def zcard(self):
        """Number of members. O(1)."""
        return len(self.scores)


# Demo: game leaderboard
lb = SortedSet()
lb.zadd("alice", 2500)
lb.zadd("bob", 1800)
lb.zadd("charlie", 3200)
lb.zadd("dave", 2100)
lb.zadd("eve", 2800)

# Get players with scores between 2000 and 3000
mid_tier = lb.zrangebyscore(2000, 3000)
print("Mid-tier players (2000-3000):")
for member, score in mid_tier:
    print(f"  {member}: {score}")

# Update a score
lb.zadd("bob", 3500)  # Bob had a great game
print(f"\nBob's new score: {lb.zscore('bob')}")  # 3500