Home / Algorithms / Article
CODECONCEPTS TECHNICAL GUIDE

Skip Lists and Disjoint Set Unions (DSU): Probabilistic Balancing and Path Compression Architecture

In advanced algorithms and distributed system design, few data structures demonstrate elegance and practical utility as vividly as Skip Lists and Disjoint Set Unions (DSU). Skip Lists replace rigid tree rebalancing mechanics (like AVL or Red-Black rotations) with probabilistic coin-toss hierarchies, forming the concurrent sorted indexing engine inside Redis Sorted Sets (ZSET) and RocksDB MemTables. Meanwhile, Disjoint Set Union provides nearly instantaneous O(alpha(N)) set connectivity queries, driving Kruskal’s Minimum Spanning Tree algorithm, network percolation simulations, and compiler type unification engines.

The Core Algorithmic Beauty
Skip Lists demonstrate that randomized algorithms can match the rigorous logarithmic performance of balanced search trees without complex rebalancing invariants. DSU illustrates how two simple heuristics—Path Compression and Union by Rank—collapse an otherwise linear tree into near-constant inverse Ackermann time.

1. The Concurrency Dilemma in Balanced Search Trees

Balanced binary search trees (such as Red-Black Trees, AVL Trees, and Splay Trees) maintain strict O(log N) depth by executing tree rotations whenever insertions or deletions violate height invariants.

While optimal in single-threaded environments, balanced trees present severe architectural bottlenecks in multi-threaded concurrent systems:

  • Lock Contention on Rotations: A single tree rotation at the root or upper internal branches alters pointers across wide subtrees, requiring coarse-grained locks that serialize concurrent readers and writers. Under heavy write traffic across dozens of CPU cores, threads spend the majority of their time stalled waiting for mutex locks.
  • Complex Lock-Free Mechanics: Implementing lock-free balanced trees with Compare-And-Swap (CAS) primitives is notoriously intricate and error-prone due to multi-node pointer dependencies and cascaded tree rebalancing phases.
  • Memory Fragmentation: Tree nodes allocated on the heap carry three or four pointers each (parent, left child, right child, metadata), creating high overhead and poor cache line locality.

William Pugh addressed this challenge in 1990 by inventing the Skip List: a probabilistic alternative to balanced trees that allows straightforward lock-free concurrent updates using fine-grained node-level CAS operations.

2. Skip List Architecture: Multi-Level Express Lanes

A Skip List is fundamentally an ordered linked list augmented with hierarchical multi-level ‘express lanes’.

Structural Hierarchy and Probabilistic Height

  • Level 0: The bottom layer containing every single element in sorted order (a standard singly-linked list).
  • Level 1: Contains approximately 1/2 of the elements from Level 0, acting as a faster express lane.
  • Level k: Contains approximately (1/2)^k of the elements, allowing giant leaps across the dataset.

Instead of enforcing structural rules, each newly inserted node chooses its height probabilistically by simulating coin flips:

def random_level(p=0.5, max_level=32):
    lvl = 1
    while random.random() < p and lvl < max_level:
        lvl += 1
    return lvl

Logarithmic Traversal Mechanics

To search for key K:

  1. Begin at the highest level of the header node.
  2. Traverse horizontally along the current express lane until the next node’s key exceeds K.
  3. Drop down one level to the corresponding node in the lower lane and resume horizontal traversal.
  4. Repeat until Level 0 is reached. If the node equals K, return success; otherwise, K does not exist.

Because higher levels skip vast numbers of intermediate elements, search, insertion, and deletion all execute in expected O(log N) time with high probability.

3. Why Production Systems (Redis and RocksDB) Prefer Skip Lists

Production systems choose Skip Lists over balanced trees for several compelling reasons:

Operational Characteristic Balanced Tree (Red-Black) Skip List
Rebalancing Strategy Deterministic rotations (alters tree shape). Probabilistic coin flips (zero structural rotations).
Concurrent Mutation Safety Requires wide subtree locks; complex lock-free CAS. Fine-grained pointer updates; simple lock-free CAS (Harris-Michael algorithm).
Memory Overhead per Node 3 pointers (parent, left, right) + 1 color bit = 25+ bytes. Average 1 / (1 – p) pointers (typically 1.33 to 2 pointers).
Range Query Performance Requires tree successor hops with parent traversal. Trivially scans forward along the flat Level 0 linked list.
Implementation Complexity Extremely high (dozens of rotation edge cases). Clean, concise, and easy to maintain.

4. Disjoint Set Union (DSU) and Union-Find Mechanics

The Disjoint Set Union (DSU) data structure, or Union-Find, tracks a collection of elements partitioned into non-overlapping (disjoint) subsets. It supports two primary operations:

  • Find(u): Determines which subset element u belongs to by returning the unique representative (root) of u’s set.
  • Union(u, v): Merges the subset containing u with the subset containing v into a single set.

The Two Fundamental Optimizations

A naive DSU implementation represents sets as parent pointers, leading to degenerate linear trees of height O(N). Two simple optimizations transform performance:

1. Union by Rank / Size: When merging two sets, attach the root of the smaller tree beneath the root of the larger tree. This limits maximum tree height to O(log N).

2. Path Compression: During a Find(u) traversal, rewrite every visited node’s parent pointer to point directly to the root:

def find(u):
    if parent[u] != u:
        parent[u] = find(parent[u])  # Path compression flattens the tree
    return parent[u]

The Inverse Ackermann Function Complexity: O(alpha(N))

When both Path Compression and Union by Rank are combined, Robert Tarjan proved in 1975 that any sequence of M operations on N elements executes in:

Amortized Time Complexity = O(alpha(N)) per operation

Here, alpha(N) is the inverse of the rapidly growing Ackermann function. For any conceivable input size in our universe (even N = 2^(2^65536)), alpha(N) is strictly less than or equal to 4! In practice, DSU operations run in effectively O(1) constant time.

5. Advanced DSU Extensions: Potential DSU and Rollback Mechanics

While standard DSU supports basic connectivity, industrial applications often require augmented invariants:

  • Weighted (Potential) DSU: Maintains relative distances or modulo equations between elements (such as parity or bipartite coloring). During path compression, weights are accumulated along the parent chain, allowing queries like “What is the difference between element A and element B?” in O(alpha(N)) time.
  • Persistent DSU and Rollback: In dynamic graph algorithms where edge removals must be rolled back (such as offline dynamic connectivity), destructive path compression cannot be used. By using Union by Rank alone, tree depth is strictly bounded to O(log N), and operations are tracked on an undo stack, allowing instant state rollbacks.

6. Enterprise Implementation: Concurrent-Ready Skip List and Optimized DSU in Python

Below is an enterprise-grade Python module implementing both an indexed Skip List and an optimized Disjoint Set Union structure with rank tracking, component sizes, and path compression:

Python 3.11 Skip List and DSU Engines
Syntax Verified
import random
from typing import Optional, List, Dict

class SkipListNode:
    def __init__(self, key: int, val: str, level: int):
        self.key = key
        self.val = val
        self.forward: List[Optional['SkipListNode']] = [None] * level

class SkipList:
    def __init__(self, max_level: int = 16, p: float = 0.5):
        self.max_level = max_level
        self.p = p
        self.header = SkipListNode(-1, "", max_level)
        self.level = 1

    def _random_level(self) -> int:
        lvl = 1
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

    def insert(self, key: int, val: str) -> None:
        update = [None] * self.max_level
        curr = self.header

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

        curr = curr.forward[0]
        if curr and curr.key == key:
            curr.val = val
            return

        new_lvl = self._random_level()
        if new_lvl > self.level:
            for i in range(self.level, new_lvl):
                update[i] = self.header
            self.level = new_lvl

        new_node = SkipListNode(key, val, new_lvl)
        for i in range(new_lvl):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def search(self, key: int) -> Optional[str]:
        curr = self.header
        for i in range(self.level - 1, -1, -1):
            while curr.forward[i] and curr.forward[i].key < key:
                curr = curr.forward[i]
        curr = curr.forward[0]
        return curr.val if (curr and curr.key == key) else None

class DisjointSetUnion:
    def __init__(self, size: int):
        self.parent = list(range(size))
        self.rank = [0] * size
        self.size = [1] * size
        self.num_sets = size

    def find(self, u: int) -> int:
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])  # Path compression
        return self.parent[u]

    def union(self, u: int, v: int) -> bool:
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u == root_v:
            return False  # Already in same set

        # Union by rank
        if self.rank[root_u] < self.rank[root_v]:
            self.parent[root_u] = root_v
            self.size[root_v] += self.size[root_u]
        elif self.rank[root_u] > self.rank[root_v]:
            self.parent[root_v] = root_u
            self.size[root_u] += self.size[root_v]
        else:
            self.parent[root_v] = root_u
            self.size[root_u] += self.size[root_v]
            self.rank[root_u] += 1

        self.num_sets -= 1
        return True

    def get_set_size(self, u: int) -> int:
        return self.size[self.find(u)]

7. Real-World Applications Across Production Systems

  • Redis Sorted Sets (ZSET): Redis implements ZSETs using a hybrid structure of a hash table (for O(1) score lookups) and a Skip List (for O(log N) range queries and ranking). The Skip List nodes store rank spans, allowing ZRANK queries in O(log N) time.
  • RocksDB MemTable: RocksDB uses an in-memory Concurrent SkipList to store uncommitted mutations. Multiple reader threads and a single writer thread operate without mutex locking.
  • Kruskal’s Minimum Spanning Tree: Kruskal’s algorithm sorts graph edges by weight and uses DSU to check whether adding an edge creates a cycle in O(alpha(V)) time.
  • Image Connected Component Labeling: Computer vision pipelines use DSU to merge adjacent foreground pixels into discrete object masks in a single linear raster scan.
  • Compiler Type Inference: Hindley-Milner type checking in functional compilers (Haskell, OCaml, Rust) utilizes DSU during the unification algorithm to equate and resolve polymorphic type variables.

8. Frequently Asked Questions (FAQ)

Q: Why does Redis use a Skip List instead of a Red-Black Tree for ZSET?

Redis creator Salvatore Sanfilippo selected Skip Lists because they are memory-efficient, simpler to implement, and support fast range scans by traversing Level 0 linked nodes without complex tree traversal. Furthermore, augmenting skip lists with ‘span’ values enables fast rank calculations.

Q: What is the probability p chosen for Skip Lists in practice?

Typically p = 0.5 (where each level has half the nodes of the previous) or p = 0.25 (used in Redis). A probability of 0.25 reduces pointer memory overhead: on average, each node contains only 1.33 forward pointers while preserving logarithmic search bounds.

Q: What is Path Compression in DSU?

Path compression is an optimization where the Find operation flattens the tree by setting every examined node’s parent pointer directly to the root, preventing trees from growing into deep degenerate linear chains.

Q: What is the difference between Union by Rank and Union by Size?

Union by Rank attaches the tree with smaller depth under the tree with greater depth. Union by Size attaches the tree with fewer total elements under the tree with more elements. Both achieve identical asymptotic bounds.

Q: Can a Skip List degrade to O(N) linear time?

Theoretically, if all coin flips return tails, a Skip List could have height 1 and behave like a standard linked list. However, the probability of this occurring on large datasets is astronomically small, and performance is guaranteed with high probability.

Q: How does DSU handle element deletions?

Standard DSU does not support simple element deletion because child nodes depend on parent representatives. Deletions require maintaining set handles with indirection nodes or re-rooting subtrees.

Q: What is the Inverse Ackermann function alpha(N)?

The inverse Ackermann function grows extraordinarily slowly. Because the Ackermann function produces incomprehensibly large numbers, its inverse never exceeds 4 for any practical input size on physical hardware.

Q: How are Skip Lists made lock-free in multi-threaded runtimes?

Lock-free Skip Lists use atomic Compare-And-Swap (CAS) instructions and marked pointers (Harris’s technique) to insert or delete forward pointers level-by-level from bottom to top without acquiring global mutex locks.

Q: Why is DSU useful for network connectivity simulations?

DSU tests whether two nodes are connected and adds connections in effectively O(1) time. This enables real-time dynamic graph connectivity tracking without re-running BFS or DFS.

Q: What is an Indexed (Rank-Augmented) Skip List?

An indexed Skip List stores the number of nodes skipped (the span) alongside each forward pointer. By summing spans during horizontal traversal, the algorithm determines the exact 1-based rank of any key in O(log N) time.

Q: Can DSU maintain additional properties like minimum edge weight per component?

Yes. By storing component metadata in the root node (such as set size, minimum weight, or maximum ID), union operations simply aggregate these attributes when linking roots together.

Q: What is DSU with Rollback (Persistent DSU)?

When solving dynamic connectivity problems where unions can be undone, path compression cannot be used because it alters tree structure destructively. Union by Rank alone maintains tree depth at O(log N) and uses a mutation stack to roll back modifications.

9. Architectural Conclusion and Engineering Recommendations

Skip Lists and Disjoint Set Unions prove that probabilistic and heuristic designs can outperform rigid structural algorithms in real-world software systems. When architecting systems:

  • Deploy Skip Lists when building concurrent sorted caches, in-memory database storage layers, or ranked leaderboards requiring lock-free scalability.
  • Leverage Disjoint Set Union (with Path Compression and Union by Rank) for graph cycle detection, network percolation modeling, and dynamic clustering workloads where near-instantaneous set queries are essential.
  • Use p = 0.25 for skip lists in memory-constrained environments to cut pointer overhead by up to 33% without compromising search performance.
TC

Taryn Crooks

Senior Codeconcepts Specialist

Senior Agricultural Researcher & Livestock Husbandry Specialist at Codeconcepts. Dedicated to advancing sustainable flock management, genetic conservation, and precision ovine nutrition.

Leave a Comment