Advanced Data Structures: From SkipLists to Segment Trees

Design Skiplist (LeetCode 1206)

A SkipList is a probabilistic data structure that allows $O(\log N)$ search, insertion, and deletion by maintaining multiple layers of linked lists. It is famously used as the underlying structure for Sorted Sets (ZSet) in Redis.

class Skiplist {
    private static final int MAX_LEVEL = 16;
    private static final double PROBABILITY = 0.5;
    private Node head = new Node(-1, MAX_LEVEL);
    private int currentLevel = 1;
    private Random random = new Random();

    static class Node {
        int val;
        Node[] next; // Array of forward pointers for each level
        Node(int val, int level) {
            this.val = val;
            this.next = new Node[level];
        }
    }

    private int randomLevel() {
        int lv = 1;
        while (random.nextDouble() < PROBABILITY && lv < MAX_LEVEL) lv++;
        return lv;
    }

    public boolean search(int target) {
        Node cur = head;
        for (int i = currentLevel - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < target) {
                cur = cur.next[i];
            }
        }
        cur = cur.next[0];
        return cur != null && cur.val == target;
    }

    public void add(int num) {
        Node[] update = new Node[MAX_LEVEL];
        Arrays.fill(update, head);
        Node cur = head;
        // Search downwards from the highest level to mark insertion points
        for (int i = currentLevel - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) cur = cur.next[i];
            update[i] = cur;
        }
        
        int lv = randomLevel();
        if (lv > currentLevel) {
            for (int i = currentLevel; i < lv; i++) update[i] = head;
            currentLevel = lv;
        }
        
        Node newNode = new Node(num, lv);
        for (int i = 0; i < lv; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
    }

    public boolean erase(int num) {
        Node[] update = new Node[MAX_LEVEL];
        Node cur = head;
        for (int i = currentLevel - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) cur = cur.next[i];
            update[i] = cur;
        }
        
        cur = cur.next[0];
        if (cur == null || cur.val != num) return false;
        
        for (int i = 0; i < currentLevel; i++) {
            if (update[i].next[i] != cur) break;
            update[i].next[i] = cur.next[i];
        }
        // Shrink currentLevel if top levels become empty
        while (currentLevel > 1 && head.next[currentLevel - 1] == null) currentLevel--;
        return true;
    }
}

Segment Tree (Interval Sum & Update)

A Segment Tree is a tree data structure used for storing info about intervals or segments. It allows querying which of the stored segments contain a given point in $O(\log N)$ time.

class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] nums) {
        n = nums.length;
        if (n > 0) {
            tree = new int[4 * n];
            build(nums, 0, 0, n - 1);
        }
    }

    private void build(int[] nums, int node, int start, int end) {
        if (start == end) {
            tree[node] = nums[start];
            return;
        }
        int mid = start + (end - start) / 2;
        build(nums, 2 * node + 1, start, mid);
        build(nums, 2 * node + 2, mid + 1, end);
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }

    public void update(int idx, int val, int node, int start, int end) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = start + (end - start) / 2;
        if (idx <= mid) update(idx, val, 2 * node + 1, start, mid);
        else update(idx, val, 2 * node + 2, mid + 1, end);
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }

    public int query(int qL, int qR, int node, int start, int end) {
        if (qR < start || end < qL) return 0;
        if (qL <= start && end <= qR) return tree[node];
        
        int mid = start + (end - start) / 2;
        return query(qL, qR, 2 * node + 1, start, mid) + 
               query(qL, qR, 2 * node + 2, mid + 1, end);
    }
}

Design Mastery Summary Table